路径状态与结构变换

◎

本节目标

区分沿路径传递的状态、子树向上返回的信息，以及安全修改树指针的顺序。

第七章公共示例树

根 1，左右孩子 2、3，节点 2 的左右孩子为 4、5。

        1
       / \
      2   3
     / \
    4   5

公共树上令目标为 7：状态沿 1 → 2 → 4 依次从 7 扣到 6、4、0，恰好在叶子 4 命中。这说明路径状态是从根向下传递的；它不同于把子树结果向上报告。

树上的递归不总是在计算一个数并返回。有些题把“走到这里以后还剩什么”从根传给子节点；有些题让当前节点拿到已经处理好的子树再改写指针。先分清状态流向，递归的入口参数、返回值和修改时机就会自然明确。

下面根为 5 的树仅是路径总和题的专用示例，用来展示更长的根到叶路径；它不是本章的公共示例树。

        5
       / \
      4   8
     /   / \
   11   13  4
   / \       \
  7   2       1

路径总和从根向下把目标值逐步扣除；求深度一类问题会让左右子树把高度向上返回；翻转和展开则直接改写每个节点的 left、right。树的形状相同，递归合同却不同。

识别信号

• 条件写成“从根到叶”的路径，当前选择会改变后续可用的目标、和或计数；
• 题目要求改变原树，或明确要求返回变换后的根节点；
• 当前节点的左右指针仍保存着后续要处理的子树，改写它们会影响递归现场；
• 结果是一条路径时，递归分支之间可能共享同一个可变容器；
• 题目不是要由子树汇总一个数值，而是要传递过程状态或重连已有节点。

问题模型与核心不变量

自顶向下的函数把状态带入子树。对路径总和，remaining 表示“进入当前节点前仍需凑出的和”；扣掉当前节点值后，只有当前节点同时是叶节点且 remaining == 0 才找到一条合法路径。状态属于这一次调用，传给左右子树的是同一数值副本，因此不需要撤销。

自底向上则相反：先让左右子树返回信息，再由父节点合并。例如最大深度让子树返回高度，当前节点取较大值再加一。它不能用“剩余目标”替代，因为需要的信息方向是从孩子回到父亲。

若用 path 这样的共享列表记录实际路径，列表属于整条 DFS 调用链：进入节点加入，离开节点删除，两个动作必须成对。只有传递整数等不可变状态时，才没有这一步回溯。

结构变换还要声明副作用。翻转递归后交换两棵已变换子树，并返回当前根；展开则以原地方式把节点重连为右链，入口返回 void / None。无论哪种方式，在覆盖指针前都必须保证仍需处理的子树已经处理或被可靠保存。

通用模板

根到叶路径状态用“进入节点时更新、叶子时判断”的合同：

hasPathSum(node, remaining):
    if node 为空:
        return false
    remaining -= node.val
    if node 是叶子:
        return remaining == 0
    return hasPathSum(node.left, remaining)
        or hasPathSum(node.right, remaining)

返回新子树根的结构变换，先取得两个递归结果，再写回当前节点：

invertTree(node):
    if node 为空:
        return 空
    left = invertTree(node.left)
    right = invertTree(node.right)
    node.left = right
    node.right = left
    return node

原地展开把“已经处理好的下一节点”保存为 previous。逆前序的右—左—根顺序保证当前节点处理时，原前序中它之后的节点已经是一条可接上的右链：

flattenDfs(node):
    if node 为空:
        return
    flattenDfs(node.right)
    flattenDfs(node.left)
    node.right = previous
    node.left = 空
    previous = node

模板变体

• 路径状态可传递剩余和、当前和、路径长度或是否已满足某个条件；只要状态按值传递，兄弟子树彼此不会污染。
• 需要输出具体路径时，用共享 path 加入当前节点、递归、删除当前节点的回溯模板；不要把可变列表本身直接保存为答案。
• 翻转这类“返回当前根”的变换适合把变换后的左右根暂存到局部变量，再统一写回。
• 展开这类原地变换可用前驱节点、尾指针或显式栈保存尚未连接的部分；本栏采用逆前序前驱，避免反复寻找子树尾部。
• 若指针修改必须在子树递归之前发生，先保存旧指针，再递归处理保存的引用；直接覆盖旧指针会使原子树不可达。

母题序列

按必学顺序练习：

1. 路径总和（必学）：用递减的剩余目标区分根到叶路径与中途命中。
2. 翻转二叉树（必学）：在两棵子树变换完成后交换根指针。
3. 二叉树展开为链表（必学）：用逆前序递归把每个节点接到已经完成的后继右链前。

常见误区

• 当前节点值已经让目标归零，就立即返回成功；路径总和要求终点是叶节点。
• 把自顶向下的 remaining 当成子树返回值，导致递归合同混乱。
• 在共享 path 返回后忘记弹出当前节点，让兄弟分支携带错误路径。
• 交换左右指针后再递归错误的那一侧，或覆盖指针后才想起原子树仍未处理。
• 展开后只检查右链上的若干值，却没有检查所有 left 都为空、节点数量没有变化以及不存在环。

迁移方向

当路径状态需要统计任意起点而不是只从根开始时，可把路径和改写为前缀和计数并在回程撤销。需要同时保留原树和新树时，结构变换改为新建节点并返回新根；需要按复杂规则重连时，再学习显式栈或链表式前驱管理。