fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
二叉树八股文：递归改迭代 :: labuladong的算法小抄
@WuYufeng233 这里我尝试去解释一下为什么这样加个visited就可以：
- 在解释之前，我们先说一个规律：在压入的stack中，如果记top=stack[0],那么stack[1]一定是top的父节点
- 首先对于之前的写法，我们一直压入左子节点，当无法压入的时候，当前栈顶元素为top，我们把top弹出，把top.right压入。而现在我们不把top弹出，直接把top.right压入，这样的话，从top开始的位置到stack的头部，一定是top子树上的节点。那这样的话，根据1的规律，每次退栈一定会出现 top.right --> top和top.left --> top的退栈顺序。
- 下面我们注意visited=stack.pop()这行代码，注意到这行代码执行后有两种情况: (1). 直接退出while，这种情况是遍历完了，我们不考虑 (2). 紧跟着执行p = stack[0]这句代码。根据1的规律，我们知道visited一定是p的子节点。这样的话就有下面两种情况： ①. visited==p.left，那说明我们left子树已经遍历完了(因为我们在回退阶段)，我们跳入中序遍历的代码块里。 ②. visited==p.right，那说明我们left子树和right子树都遍历完了(因为我们在回退阶段并且左子树已经比右子树先遍历完)
- 至此分析完毕。
东哥，这还是不会用呀，只是用迭代的方式遍历二叉树还好。但是如果是在递归方式中，左右子树有返回值，然后在后序遍历位置根据左右子树返回值处理的类型，就不会用了。比如leetcode543题，这个根据左右子树的值然后在迭代方式中的后序位置怎么用呢，关键是怎么得到左右子树的结果？
@aristo-panhu 嗯，这确实是一个比较复杂的问题，所以我说递归改迭代是一个套路题，实际应用中不怎么会用到。非要利用左右子树的结果的话，需要把每次递归的返回值也存到栈里，这就是完全模拟计算机处理递归函数的过程了。
python后序遍历迭代代码
stack = []
# 左侧树枝一撸到底
def pushLeftBranch(p):
while (p != None):
# 前序遍历代码位置
################
################
stack.append(p)
p = p.left
def postOrderTraversal(root):
postorder = []
# 指向上一次遍历完的子树根节点
visited = TreeNode()
# 开始遍历整棵树
pushLeftBranch(root)
while (len(stack) > 0):
p = stack[-1]
# p 的左子树被遍历完了，且右子树没有被遍历过
if (p.left == None or p.left == visited) and p.right != visited:
# 中序遍历代码位置
#############
#############
pushLeftBranch(p.right)
# p 的右子树被遍历完了
if p.right == None or p.right == visited:
# 后序遍历代码位置
####################
postorder.append(p.val)
####################
visited = stack.pop()
return postorder
