子树信息与递归判断

◎

本节目标

从空树的返回值出发，让子树向父节点报告高度、镜像关系或失败状态。

第七章公共示例树

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

        1
       / \
      2   3
     / \
    4   5

递归树题的关键不是先写出递归调用，而是先说清一棵子树能向父节点报告什么。根节点的左右子树先各自完成报告，父节点再把两份报告合并。这样，递归调用的含义、空树边界与整棵树答案都可以逐层检查。

识别信号

• 当前节点的结论依赖左右子树已经计算出的信息；
• 题目询问高度、是否满足某个结构条件，或经过当前节点的最优值；
• 空节点必须有明确且可合并的返回值；
• 发现一棵子树失败后，希望立刻向上停止无效计算；
• 当前节点需要更新答案，但父节点仍只需要其中一部分信息。

问题模型与核心不变量

公共树中，dfs(2) 可报告高度 2，dfs(3) 报告高度 1；根 1 合并后报告高度 3。这正是子树报告先到父节点、再由父节点合并的过程。

把函数 dfs(node) 定义为“节点 node 为根的子树向父节点的报告”。空树的报告通常是 0，因为空树高度为零，且不会增加直径。左右子树报告到达当前节点后，当前节点只做一次确定的合并：取最大高度、镜像配对比较，或检查高度差。

写递归前，先补全一句接口说明：dfs(node) 返回什么，空树又返回什么。返回值可以是高度、布尔判断、失败标记，或一个包含多份信息的小状态；但同一字段在每一层必须保持同一种含义。这样“子树报告—当前节点合并—向父节点继续报告”的职责才不会混淆。

要区分两种结果。最大深度的返回值就是答案；平衡树的返回值既携带高度，也可用 -1 携带失败；直径的递归返回值始终是高度，但直径要在每个节点由左右高度相加后更新。把这些职责混在一起，常会把“经过当前节点”的路径误当作“能继续向父节点延伸”的路径。

通用模板

dfs(node):
    if node 为空:
        return 空树报告

    leftInfo = dfs(node.left)
    rightInfo = dfs(node.right)
    在当前节点合并 leftInfo 与 rightInfo
    return 当前子树需要向父节点报告的信息

先定义空树返回什么，再定义报告的语义。只有这两件事明确，左右递归和当前合并才有可验证的含义。若报告中有失败状态，应在得到它后立即返回，避免继续计算已经不可能恢复的子树。

模板变体

• 最大深度返回左右高度的较大值加一，报告与整棵树答案相同。
• 对称判断把接口改为 mirror(left, right)，同时比较两棵应互为镜像的子树。
• 平衡树把高度和失败状态编码进一个整数，-1 一旦出现便直接向上传播。
• 直径让递归只返回高度，在当前节点用 leftHeight + rightHeight 更新外部答案；路径长度按边数计算。
• 若当前节点要同时汇合两侧的节点信息，则把“找到的节点或空”作为报告；这种左右信息首次汇合的情形会在树上综合问题中继续练习。

母题序列

按必学顺序练习：

1. 二叉树的最大深度（必学）：从高度返回值建立最小递归模型。
2. 对称二叉树（必学）：同时维护两个镜像位置的递归接口。
3. 平衡二叉树（必学）：用特殊返回值把失败状态提前带回父节点。
4. 二叉树的直径（必学）：区分向上返回的高度和在当前节点更新的全局答案。

常见误区

• 没有先定义空树返回值，导致叶子和空指针处出现互相矛盾的特判。
• 对称判断只比较左右孩子的值，没有交叉比较左的左与右的右。
• 平衡树先计算完整高度，再自顶向下重复检查，造成不必要的重复遍历。
• 直径把节点数当作边数，或把左右高度之和直接返回给父节点。
• 把一次调用的全局答案留到下一次调用，破坏平台对象的可重用性。

迁移方向

当父节点需要从子树接收多个字段时，可以让递归返回一个明确的结构；当路径状态从根向下传递时，则转向下一栏的路径状态模型。更复杂的树形动态规划、换根 DP 与树上数据结构不属于本章范围。