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
