LeetCode 101 对称树之外：二叉树的三种遍历与「递归的顺序感」

三种遍历：处理时机的三种选择

二叉树的递归遍历，骨架完全相同，差别只在「处理节点的时机」：

def traverse(root):
    if not root:
        return
    # 处理 root          ← 前序（进入时）
    traverse(root.left)
    # 处理 root          ← 中序（左子树后）
    traverse(root.right)
    # 处理 root          ← 后序（离开前）

「前中后」的命名依据：处理节点相对于「左右子树遍历」的位置——「处理时机」的三种选择——「选择处理时机」就是选择解题策略**：

前序（进入时）：「自顶向下」的信息传递——父节点的信息先于子节点可用——「深度、路径、复制树」——LeetCode 104 的深度递传（depth+1 下传）、「路径累积」（257 二叉树的所有路径——path 的追加在进入时——「自顶向下的 DP」（树形 DP 的向下形态）。中序（左后）：「BST 的有序性」——BST 的中序遍历输出升序序列——「中序+BST」的组合：验证 BST（98）、第 K 小元素（230）、「BST 的修复」（99 恢复二叉搜索树——「BST 的性质在中序中显形」——「发现节点逆序对」定位交换的两节点——「中序前驱」的概念。后序（离开前）：「自底向上」的信息汇总——子节点的信息先于父节点可用——「高度、直径、最大路径和」——LeetCode 124（库内已有）的路径和——「子树的信息聚合」——「后序 = 树形 DP 的标配」——「树形 DP 的转移依赖子树结果」——「后序是树形 DP 的物理必然」。

graph TD
    A[前序: 进入时处理<br/>自顶向下传递<br/>深度/路径/复制] --> D[选择依据:<br/>信息流向]
    B[中序: 左后处理<br/>BST 有序性<br/>验证/第K小] --> D
    C[后序: 离开前处理<br/>自底向上汇总<br/>高度/直径/树形DP] --> D

「遍历顺序」的解题实例

实例一：最大深度（LeetCode 104）——「后序的必要性」——max depth = max(左深, 右深) + 1——「需要子树的结果」——「先递归后计算」——「后序」的形态——「写成前序会怎样」（传 depth+1 的自顶向下也能做（「两种传信息的方向」：向下传状态（前序参数）、向上传结果（后序返回值——「信息的方向」决定遍历的选择——「树形 DP 的两个子类」。

实例二：验证 BST（LeetCode 98）——「中序的运用」——BST 中序有序——「中序遍历中检查递增」——「prev 变量」（记录前一个节点——「递归中的跨层比较」——「prev 的维护」——「BST 验证的另一个方法」（上下界的传递（「min/max 限界」的自顶向下——「两种验证」的对比——「中序法」简洁、「限界法」直观——**「发现中序逆序对」的修复思路（99 题。

实例三：树的直径（LeetCode 543）——「后序的聚合」——直径 = 左深+右深——「每个节点作为『拐弯点』」——「直径的更新在递归中」（ans = max(ans, left+right)——「返回值」是深度、「更新值」是直径——「返回值与全局答案的分离」——「树形 DP 的经典模式」：递归返回「局部信息」、全局变量维护「最终答案」——「这个模式」在二叉树最大路径和（库内 124 题）中完全相同——「124 是 543 的进阶」——「模式一致、信息不同」。

「遍历顺序」与题目类型的匹配表

匹配表：「前序」适合——复制树、序列化（「序列化的前序」（空节点标记——「重建树」、路径类、删除子树（「自顶向下的决策」——「判断要不要继续」先于子树。「中序」适合——BST 相关（验证、第 K 小、前驱后继、「排序输出」——「BST 与中序的绑定」是最强关联。「后序」适合——高度/深度/直径/路径和、「需要销毁或合并」（释放内存（「先处理孩子再处理自己」——「自底向上的统计」——「树形 DP 的默认形态」。「不确定时的策略」：「信息从哪来」——答案依赖子树结果→后序；答案沿路径传递→前序；需要有序→中序——「问自己：这个节点的处理，需要子树先算完吗？」**——一句话判断遍历顺序。

递归的修行路径：写不出的破法、算不清的账与跑不深的栈

「看题解都懂，自己动笔就写不出——怎么破？」——这是递归学习的头号卡点，破法是把「写递归」降级成一道填空题，固定四步走。第一步：先定语义。动笔前用一句话说清「这个函数接收什么、返回什么」——「depth(root) 返回以 root 为根的树的最大深度」——语义说不清的递归必然写错，这一句还会决定后面「当前层怎么用子结果」；本篇三种遍历的语义各自是「输出进入/经过/离开时的节点序列」，一句话定下处理时机。第二步：写终止。枚举「不用递归就能直接回答的最小输入」——空树返回空序列、空树深度为 0——终止条件漏写是空指针，多写是漏解，两个方向都要审。第三步：只写当前层。假设两个递归调用已经返回了正确结果，问自己「怎么用这两个结果拼出当前的答案」——深度是 max(左, 右) + 1，直径是「左深 + 右深」更新全局、返回值仍传深度——当前层只做拼装，不做展开。第四步：小例子验证。两三层的小树手动走一遍，语义、终止、拼装三件套互相印证。拿「前序复制树」演练一遍：语义是「copy(root) 返回一棵与 root 等价的新树」；终止是空树返回 None；当前层是「新建节点、值取 root 的值、左右孩子分别 copy 左右子树」；两层小树走一遍——四步走完代码已经写完，全程没有展开过任何一层递归。这四步的底层是数学归纳法：归纳法从不逐层展开，只用「假设 n−1 成立推出 n 成立」；递归同理——「假设子调用正确」不是偷懒，是归纳假设，你信任的是「语义在每一层都一致」这件事本身。「递归的复杂度怎么算清？」——树类问题用节点计数法：每个节点被访问几次、单次花多少时间——三种遍历里每个节点恰好处理一次、单次常数，答案 O(n)；更一般的递归式：T(n) = 2T(n/2) + O(1)，画递归树（每层的代价之和、总层数）或套主定理——但手画一次递归树的收获大于背十遍主定理。必须额外警惕重复子问题：斐波那契的裸递归是指数级，因为同一个子问题被成千上万次重算；树的子树互不重叠，天然没有这个问题——「子问题重叠吗」是递归复杂度的第一问：重叠就上记忆化（@cache 一行把指数打成线性），不重叠就别浪费缓存。「递归深度有限制吗？」——有，而且是工程红线：Python 默认上限约一千层，sys.setrecursionlimit 只是调整炸弹的当量；JVM 取决于线程栈大小与帧体积；十万节点的链状树在任何语言裸递归都会爆栈——这正是姊妹篇「显式栈迭代化」存在的理由。顺带澄清尾递归：把递归写成「函数的最后一个动作」理论上可复用栈帧，但 Python 明确不做尾调用优化、Java 也不保证——尾递归是写法，优化是编译器的施舍，不能当依赖。「写完递归怎么自检？」——四个检查点：终止条件是否覆盖所有空形态；返回值语义与每个调用处的用法是否一致（最常见的 bug 是「有的分支忘了 return」，静默返回 None 污染上层）；当前层是否真的用了子结果（写了递归却把返回值扔掉的「假递归」）；全局变量与返回值是否混用——直径题的「返回深度、全局记答案」是正确示范，混用则是灾难源。「这套修行与三种遍历的关系」：四步法里唯一随题目变化的，是第三步「当前层的工作」放在骨架的哪个位置——前序放最前、中序放中间、后序放最后——终止条件与递归调用在三种遍历里一字不差。把骨架默写到条件反射，剩下的「选时机」就是正文匹配表的全部内容：需要子树结果吗（后序）、沿路径传状态吗（前序）、要有序吗（中序）。递归的修行不是刷一百道题，是把同一副骨架的十道变奏写到不再需要思考骨架本身——那时你的注意力才腾得出来，放在真正解题的部分。

「三种遍历能互相还原出彼此吗？」——引申一个经典追问：给前序 + 中序可以唯一重建树（105 题），后序 + 中序也可以（106 题），但前序 + 后序不能——反例是单孩子节点：孩子只有一个时，它在前序里是根的下一个、在后序里是根的前一个，但它到底是左孩子还是右孩子无法区分——根因仍是「单个序列丢结构」：两个序列必须「一个管根的分割、一个管左右子树的归属」才能钉死结构，中序恰好提供「根左边全是左子树、右边全是右子树」的归属信息，这就是它不可替代的原因。由此记住一个实用推论：重建类题目的复杂度是 O(n)——每个节点只被分区一次，用哈希表把「值 → 中序下标」预存起来，分区判断从扫描降为查表。把这道追问放在三种遍历之后刚好闭环：遍历是「树 → 序列」的投影，重建是「序列 → 树」的逆变换，而「哪些投影可逆」正是三种遍历最深刻的一道延伸题。

小结

二叉树遍历的完整认知：三种遍历是「处理时机的三种选择」（前序=自顶向下传信息、中序=BST 的有序性、后序=自底向上汇信息）；解题实例（最大深度的后序、验证 BST 的中序、直径的「返回值与全局答案分离」模式）；匹配表（按「信息的流向」选择遍历——「需要子树结果吗？需要有序吗？沿路径传状态吗？」三问定遍历）；树形 DP 的形态（后序是默认、前序是自顶向下变体——「124 与 543」的模式传承）。给学习者的提醒：「遍历顺序的选择」本身就是解题的一部分——很多树题卡壳的原因不是「不会递归」，是「在该用后序的地方用了前序」——「信息流向」的诊断意识——先问「子树的结果需要吗」，答案决定遍历——「遍历即策略」——这是从「会背三种遍历」到「会用三种遍历」的进化。

三种遍历不是三个套路，是「同一个递归骨架的三个处理时机」——掌握「时机即策略」的视角，树的题目就从「背模板」变成「选策略」。