专题进阶 · 树与范围查询推荐总顺序 · 第 47 / 148 课

用展开标记表达先处理孩子再处理根,连接子树汇总与树形 DP。

先学会这些,再进入本课 二叉树 前序遍历
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

后序遍历Postorder

先处理孩子再处理根,适合用子树结果合成父节点答案。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用展开标记表达先处理孩子再处理根,连接子树汇总与树形 DP。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 展开任务将根的完成任务放到所有孩子任务之后。
  2. 孩子各自遵守同一规则,递归地保证后序。
  3. 每个节点只创建一次完成任务,所以恰好输出一次。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

表达式树根为乘号,左右是 2+3 与 4,后序如何计算?

需要一点提示

先计算两个操作数。

查看解析与答案

左子树得 5,右子树得 4,再做 5×4=20。

练习 2 · 边界与辨析

后序最后一项是谁?

需要一点提示

根等待所有孩子。

查看解析与答案

非空树的根。

练习 3 · 变式与迁移

计算每个子树节点数需要保存什么?

需要一点提示

根要读到孩子结果。

查看解析与答案

可在递归返回值中携带计数,或在迭代完成时把结果写入以节点为键的表。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。