二叉树遍历的循环解
2019-07-22 本文已影响0人
霍尔元件
94 Binary Tree Inorder Traversal
二叉树中序遍历的循环解
常规思路：
向左找到尽头，弹出一个节点，指针指向弹出节点的右孩子 继续循环
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# if not root:
# return []
res, stack = [], []
p = root
while stack or p: # 中序遍历处理完左侧分支和根节点之后 栈空 所以只用stack做条件不合理
while p:
stack.append(p)
p = p.left
cur = stack.pop() # 左边走到尽头 弹出最左节点
res.append(cur.val)
# while stack and not cur.right: # 希望弹出的节点的右孩子存在 这样就找到一个接盘侠 类似于递归的感觉
# cur = stack.pop() # 但是你怎么能保证就存在呢? p 还是有可能是空的 所以不用折腾
# res.append(cur.val)
p = cur.right # 很像递归
return res
将两层while循环简化成一层 仔细分析和上面的代码思路一抹一样
def inorderTraversal(self, root):
res, stack = [], []
p = root # 定义一个指针
while stack or p:
if p: # 进栈 往左
stack.append(p)
p = p.left
else: # 出栈 往右 (左边走到尽头)
node = stack.pop()
res.append(node.val)
p = node.right # 尝试向右边跑 如果这个节点存在 就是递归 不存在 就继续弹出栈内节点
return res
节点状态标记法
中序遍历顺序：左根右
难点在于访问到根节点的时候并不是现在就要处理该节点（打印该节点）
而是要去该节点的左孩子继续向下访问，
只有当左孩子部分全部处理完毕，再次访问到根节点的时候才是处理根节点的时候
所以给每一个节点设置一个状态，用于标记该节点之前是否见过，当某个节点第二次访问的时候就是该处理的时候
def inOrder(root):
res, stack = [], [(root, False)]
while stack:
node, vis = stack.pop()
if node:
if vis:
res.append(node.val)
else: # 注意堆栈元素顺序和根左右恰好相反
stack.append((node.right, False))
stack.append((node, True))
stack.append((node.left, False))
return res
二叉树前序遍历、后序遍历循环解 leetcode 144 145
对于前序遍历，因为根节点一开始就被用掉，所以很方便
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
# pre-order, right first 这样left位于栈顶 所以是根左右
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res
对于后序遍历 根节点最后处理 所以需要一直在栈底
节点状态标记法
对于每一个节点给一个状态，用于标记这个节点是第一次访问还是第二次访问，第二次访问才是真正处理该节点的时候（打印该节点）
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [(root, False)]
while stack:
node, vis = stack.pop()
if node:
if vis: # 左右孩子处理完毕
res.append(node.val)
else:
stack.append((node, True)) # 成功地将根节点放在了栈底
stack.append((node.left, False))
stack.append((node.right, False))
return res
