大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一个帖子，一个同学在面试理想汽车的时候，面试官问他二叉树后续遍历的流程，结果他俩各执己见，互相都很确定自己是正确的，下面是帖子的原文。
评论区更是惊现了神评论，虎哥也是笑喷了。
其实在我们面试的时候，和面试官有效沟通是很重要的，不是只能面试官向候选人提问，候选人在有疑问的时候也可以让面试官详细讲讲他的见解，在这种一来一回的交流中也会加深候选人对面试官所提问题的思考。面试的大忌就是这种和面试官各执己见，最终的结果不用想都知道。大家有没有类似的经历，可以在评论区说说自己的经历。
讲到面试，最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们就讲一下二叉树的后序遍历。
基础回顾
后续遍历的流程如下：
先访问左子树； 再访问右子树； 最后访问根节点。
下面我们给出递归法和迭代法两种代码实现。
python代码实现
递归法的实现比较直观，我们直接给出代码。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def postorderTraversal(root):
"""
:param root: TreeNode
:return: List[int]
"""
if not root:
return []
# 后序遍历左子树
left = postorderTraversal(root.left)
# 后序遍历右子树
right = postorderTraversal(root.right)
# 访问根节点
return left + right + [root.val]
# 构建一棵树
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
# 后序遍历
print(postorderTraversal(root)) # 输出[2, 3, 1]
对于迭代法，我们使用一个栈来模拟递归的过程。
首先将所有左子树入栈，然后开始处理栈顶元素。如果栈顶元素有右子树，并且它不是上一次访问的节点，则将右子树的所有左子树入栈，否则访问栈顶元素并将其出栈。重复这个过程直到栈为空。
def postorderTraversal(root):
"""
:param root: TreeNode
:return: List[int]
"""
if not root:
return []
stack, output = [], []
while root or stack:
# 遍历到最左边的节点
while root:
stack.append(root)
root = root.left if root.left else root.right
# 此时root为空，说明已经到达左下角
node = stack.pop()
output.append(node.val)
# 如果当前节点是上一个节点的左子节点，则转向同父的右子节点
if stack and stack[-1].left == node:
root = stack[-1].right
else:
# 否则，继续弹栈
root = None
return output
# 使用递归法中的例子进行测试
print(postorderTraversal(root)) # 输出[2, 3, 1]
今天的分享就到这里，希望大家有所收获！
