01先把问题说具体
删除整棵树、求子树高度或计算表达式,都需要孩子完成后才能处理父节点。怎样安排这个顺序?
02一步步得到方法
后序是计算依赖的自然顺序
顺序为左、右、根。父节点的结果依赖两个孩子时,前序访问太早,中序仍缺右子树结果,后序恰好在两边都完成后合并。二叉树高度公式就是最简单的树形动态规划。
递归返回点天然对应后序。迭代版本为每个任务增加 expanded 标记:False 表示尚需展开孩子,True 表示孩子已安排完成,现在可以访问根。
将递归调用拆成两个时刻
第一次遇到节点,先把它的 True 任务压回栈,再压右 False、左 False。因为栈后进先出,实际执行顺序是左、右、最后根。不要把再次压栈误认为重复输出。
子问题先完成,父问题才汇总
后序先遍历左右子树,再处理根,因此自然对应树高、子树大小、树形 DP 等“父节点依赖孩子结果”的计算。把处理动作放到两次递归之后,就明确了依赖次序。
显式栈需要区分第一次看到节点和孩子处理完再次回到节点。可以记录访问标记,或使用其他等价方法;只把前序的访问顺序倒过来时,要同时核对左右孩子次序。
03把一个小例子完全算清楚
树 4(2(1,3),7)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 展开根 4 | 依次安排 4完成、7展开、2展开 | 根要等待 |
| 完成左子树 | 输出 [1,3,2] | 孩子先于 2 |
| 完成右子树与根 | 输出 [1,3,2,7,4] | 最后才输出 4 |
窄屏可左右滑动表格,阅读完整计算与理由。
每个节点经历展开和完成两个状态,只有完成时才输出。
04为什么这个方法成立
- 展开任务将根的完成任务放到所有孩子任务之后。
- 孩子各自遵守同一规则,递归地保证后序。
- 每个节点只创建一次完成任务,所以恰好输出一次。
05把推导翻译成代码
Python · 可独立运行的教学实现
def postorder(tree):
stack, output = [(tree, False)], []
while stack:
node, expanded = stack.pop()
if node is None:
continue
value, left, right = node
if expanded:
output.append(value)
else:
stack.append((node, True))
stack.append((right, False))
stack.append((left, False))
return output逐个理解关键决定
(node, True)- 表示孩子处理完后回到这里,不是再次递归展开。
if node is None- 统一跳过空孩子,使叶子无需额外分支。
06时间、空间与实现范围
每个节点常数次入栈,时间 O(n),显式待办栈 O(h),输出 O(n)。
若改用两栈或反转完整前序列表,也能得到后序,但额外工作存储可能为 O(n)。
07改变条件,检查哪里会出错
先释放父节点再读取孩子指针
在手动内存管理语言会访问已释放对象;后序正是安全释放顺序之一。
释放节点后才读取其孩子
在需要手动管理内存的语言中,应先完成孩子处理再释放父节点,避免访问已失效节点。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
表达式树根为乘号,左右是 2+3 与 4,后序如何计算?
需要一点提示
先计算两个操作数。
查看解析与答案
左子树得 5,右子树得 4,再做 5×4=20。
后序最后一项是谁?
需要一点提示
根等待所有孩子。
查看解析与答案
非空树的根。
计算每个子树节点数需要保存什么?
需要一点提示
根要读到孩子结果。
查看解析与答案
可在递归返回值中携带计数,或在迭代完成时把结果写入以节点为键的表。