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用于存儲暫時移出循環(huán)的右兒子們. 然后在root或者stack不為空的時候, 進(jìn)行循環(huán). 在循環(huán)中, 每當(dāng)發(fā)現(xiàn)左兒子存在, 則1. 將右兒子壓入stack, 2. 將root的左兒子傳遞到右兒子, 3. 將root的左子樹設(shè)為None. 然后向右兒子進(jìn)發(fā)一步; 當(dāng)沒有左兒子時, 如果右兒子存在, 則向右進(jìn)一步, 如果沒有, 則從stack中取出一個stand-by的節(jié)點.

"""
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