LintCode: Flatten Binary Tree to

Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.

思路: 定义一个空的stack用于存储暂时移出循环的右儿子们. 然后在root或者stack不为空的时候, 进行循环. 在循环中, 每当发现左儿子存在, 则1. 将右儿子压入stack, 2. 将root的左儿子传递到右儿子, 3. 将root的左子树设为None. 然后向右儿子进发一步; 当没有左儿子时, 如果右儿子存在, 则向右进一步, 如果没有, 则从stack中取出一个stand-by的节点.

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    # @param root: a TreeNode, the root of the binary tree
    # @return: nothing
    def flatten(self, root):
        # write your code here
        stack = []
        h0 = root
        while stack or root:
            if not root:
                root = stack.pop()
            else:
                if root.left:
                    if root.right:
                        stack.append(root.right)
                    root.right = root.left
                    root.left = None
                elif root.right:
                    pass
                else:
                    if stack:
                        root.right = stack.pop()
                root = root.right
        return h0