05 分治在二叉树：重建与最长路径

分治在二叉树：重建与最长路径

摘要

二叉树是分治法最自然的舞台——树的递归结构天然地将问题分解为左子树和右子树两个独立的子问题，无需任何”人为分割”。本文深度剖析四道面试高频题：LeetCode 105（从前序与中序遍历序列构造二叉树）、LeetCode 106（从中序与后序遍历序列构造二叉树）、LeetCode 543（二叉树的直径）和 LeetCode 124（二叉树中的最大路径和）。这四道题由浅入深，揭示了树上分治的两种核心模式：重建分治（利用遍历序列递归重建树结构）和路径分治（在每个节点汇聚左右子树的信息，计算跨越该节点的最优值）。

---

第 1 章 二叉树天然是分治问题

1.1 为什么树适合分治

在数组上做分治，需要人为选定”中点”作为分割边界。但在二叉树上，根节点天然就是分割点：

• 根节点本身是一个局部问题
• 左子树和右子树是两个完全独立的子问题（不共享任何节点）
• 处理完左右子树后，在根节点处合并（汇聚）两侧的信息

这种结构让”分治”在树上是”免费的”——你只需要写好递归函数，框架自动完成分解和合并。

1.2 树上分治的通用框架

Result solve(TreeNode root) {
    // 基础情形：空节点
    if (root == null) return baseCase();
 
    // 分解：递归求解左子树和右子树
    Result leftResult = solve(root.left);
    Result rightResult = solve(root.right);
 
    // 合并：在根节点处汇聚左右子树的结果
    return combine(root, leftResult, rightResult);
}

关键在于 Result 的设计：不同的问题需要返回不同的信息。设计好”每个子树返回什么信息给父节点用”，是树上分治的核心技能。

1.3 本文四道题的统一视角

题目	问题类型	每个节点返回什么	合并逻辑
LeetCode 105	重建树	构建好的子树根节点	将根节点连接到左右子树
LeetCode 106	重建树	构建好的子树根节点	同上，后序确定根，中序确定左右范围
LeetCode 543	路径最长	以该节点为端点的最长单臂路径长	左臂 + 右臂 = 直径，更新全局最大
LeetCode 124	路径最大和	以该节点为端点的最大单臂路径和	左臂 + 根 + 右臂 = 跨越路径，更新全局最大

---

第 2 章 LeetCode 105：从前序与中序序列构造二叉树

2.1 题目

LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal（中等）

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出:
    3
   / \
  9  20
    /  \
   15   7

说明：树中没有重复的元素。

2.2 先序遍历和中序遍历各自告诉我们什么

先序遍历（preorder = root → left → right）：序列的第一个元素始终是当前子树的根节点。

中序遍历（inorder = left → root → right）：根节点将序列分成两部分——左侧全是左子树的节点，右侧全是右子树的节点。

这两个性质结合起来，就是重建算法的全部：

1. 从 preorder[0] 确定根节点的值（设为 rootVal）
2. 在 inorder 中找到 rootVal 的位置（设为 inIndex）
3. inorder[0..inIndex-1] 是左子树的中序遍历，共 leftSize = inIndex 个节点
4. preorder[1..leftSize] 是左子树的先序遍历（先序根后紧跟左子树）
5. inorder[inIndex+1..] 是右子树的中序遍历
6. preorder[leftSize+1..] 是右子树的先序遍历
7. 递归重建左右子树，连接到根节点

2.3 实现细节：用哈希表加速定位

每次在 inorder 中查找 rootVal 如果是线性扫描，是 $O(n)$，总体复杂度 $O(n^2)$。用哈希表预处理，查找降为 $O(1)$，总体 $O(n)$。

class Solution {
    private Map<Integer, Integer> inorderIndexMap;  // 值 → 在 inorder 中的下标
 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 预处理：构建 inorder 的值→下标哈希表
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
 
        return build(preorder, 0, preorder.length - 1,
                     inorder, 0, inorder.length - 1);
    }
 
    /**
     * 用 preorder[preLeft..preRight] 和 inorder[inLeft..inRight] 重建子树
     * 这两个范围始终对应同一棵子树
     */
    private TreeNode build(int[] preorder, int preLeft, int preRight,
                           int[] inorder, int inLeft, int inRight) {
        // 基础情形：空子树
        if (preLeft > preRight) return null;
 
        // 先序序列的第一个元素是当前子树的根
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
 
        // 在中序序列中找根的位置
        int inIndex = inorderIndexMap.get(rootVal);
 
        // 左子树的节点数量
        int leftSize = inIndex - inLeft;
 
        // 递归重建左子树
        // 左子树先序：preorder[preLeft+1 .. preLeft+leftSize]
        // 左子树中序：inorder[inLeft .. inIndex-1]
        root.left = build(preorder, preLeft + 1, preLeft + leftSize,
                         inorder, inLeft, inIndex - 1);
 
        // 递归重建右子树
        // 右子树先序：preorder[preLeft+leftSize+1 .. preRight]
        // 右子树中序：inorder[inIndex+1 .. inRight]
        root.right = build(preorder, preLeft + leftSize + 1, preRight,
                          inorder, inIndex + 1, inRight);
 
        return root;
    }
}

复杂度：

• 时间：$O(n)$，每个节点恰好被处理一次
• 空间：$O(n)$，哈希表 + 递归栈（最坏情况下树退化为链，栈深度 $O(n)$）

2.4 下标推导的可视化

以 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7] 为例：

第一次调用：
  preorder[0..4]，inorder[0..4]
  rootVal = preorder[0] = 3
  inIndex = inorderIndexMap[3] = 1
  leftSize = 1 - 0 = 1

  左子树：
    preorder[1..1]（即 [9]），inorder[0..0]（即 [9]）
    rootVal = 9，inIndex = 0，leftSize = 0
    → 叶节点 9

  右子树：
    preorder[2..4]（即 [20,15,7]），inorder[2..4]（即 [15,20,7]）
    rootVal = 20，inIndex = 3，leftSize = 3 - 2 = 1
    
    左子树：preorder[3..3]（[15]），inorder[2..2]（[15]）→ 叶节点 15
    右子树：preorder[4..4]（[7]），inorder[4..4]（[7]）→ 叶节点 7

最终构建出正确的树结构。

---

第 3 章 LeetCode 106：从中序与后序序列构造二叉树

3.1 题目

LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal（中等）

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

输入: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出: 与 105 相同的树（根为 3）

3.2 后序遍历的特性

后序遍历（postorder = left → right → root）：序列的最后一个元素始终是当前子树的根节点。

这是与前序遍历对称的特性。重建算法与 105 几乎完全对称，只需将”取 preorder 第一个元素”改为”取 postorder 最后一个元素”，并相应调整左右子树的范围计算。

3.3 实现

class Solution {
    private Map<Integer, Integer> inorderIndexMap;
 
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                     postorder, 0, postorder.length - 1);
    }
 
    private TreeNode build(int[] inorder, int inLeft, int inRight,
                           int[] postorder, int postLeft, int postRight) {
        if (postLeft > postRight) return null;
 
        // 后序序列的最后一个元素是当前子树的根
        int rootVal = postorder[postRight];
        TreeNode root = new TreeNode(rootVal);
 
        int inIndex = inorderIndexMap.get(rootVal);
        int leftSize = inIndex - inLeft;
 
        // 左子树
        // 左子树中序：inorder[inLeft..inIndex-1]
        // 左子树后序：postorder[postLeft..postLeft+leftSize-1]
        root.left = build(inorder, inLeft, inIndex - 1,
                         postorder, postLeft, postLeft + leftSize - 1);
 
        // 右子树
        // 右子树中序：inorder[inIndex+1..inRight]
        // 右子树后序：postorder[postLeft+leftSize..postRight-1]（排除末尾的根）
        root.right = build(inorder, inIndex + 1, inRight,
                          postorder, postLeft + leftSize, postRight - 1);
 
        return root;
    }
}

设计哲学：105 和 106 的统一视角

两道题的本质完全相同：在遍历序列中定位根节点，利用中序遍历分离左右子树范围。区别只在于根节点的位置：先序在最前，后序在最后。

为什么没有”先序 + 后序”重建？因为先序序列只告诉我们根在哪里，后序序列也只告诉我们根在哪里，两个信息都没有”左右子树的分界线”。中序序列才提供分界线，这是中序序列的不可替代性。

---

第 4 章 LeetCode 543：二叉树的直径

4.1 题目

LeetCode 543 - Diameter of Binary Tree（简单）

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。此路径可能经过也可能不经过根节点。

两节点之间路径的长度由它们之间边的数目表示。

输入: root = [1,2,3,4,5]
输出: 3
解释: 3，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度

输入: root = [1,2]
输出: 1

4.2 关键洞察：直径经过某个节点

对于树中任意一条路径，它都有一个”最高点”——路径上最靠近根的那个节点。这条路径可以分为两部分：

• 从最高点到路径一端的单臂路径（向左子树延伸）
• 从最高点到路径另一端的单臂路径（向右子树延伸）

因此，最长路径 = 某个节点的”最长左臂” + “最长右臂”。

算法设计：

• 对每个节点，定义 depth(node) = 以该节点为根的子树中，从该节点出发的最长路径长度（单臂）
• 对每个节点，计算 depth(left) + depth(right)（经过该节点的最长路径），更新全局最大值
• 返回 1 + max(depth(left), depth(right))（向父节点汇报的单臂长度）

4.3 分治实现

class Solution {
    private int maxDiameter = 0;  // 全局最大直径
 
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxDiameter;
    }
 
    /**
     * 返回以 node 为端点的最长单臂路径长（边数）
     * 副作用：更新全局最大直径
     */
    private int depth(TreeNode node) {
        if (node == null) return 0;  // 空节点：单臂长度为 0
 
        // 分解：递归求左右子树的最长单臂长度
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
 
        // 合并：经过 node 的最长路径 = 左臂 + 右臂
        // 更新全局最大直径
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
 
        // 返回给父节点的单臂长度：1（node 本身这条边）+ 左右两侧中更长的那个
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

4.4 为什么不是”从根出发的最长路径”

初学者常见误区：以为直径 = 从根出发的最长路径。这是错误的。

反例：

        1
       / \
      2   3
     / \
    4   5
   / \
  6   7

直径是从 6（或 7）到 5 的路径：6 → 4 → 2 → 5，长度为 3。这条路径的最高点是节点 2，不是根节点 1。

如果只从根出发，最长路径是 1 → 2 → 4 → 6（或 7），长度为 3，这里碰巧也是 3，但这只是巧合。考虑更极端的情形：

    1
   /
  2
 / \
3   4
 \   \
  5   6

直径是 5 → 3 → 2 → 4 → 6，长度为 4。最高点是节点 2，不是根节点 1。

结论：必须对每个节点都计算”经过该节点的直径”，取全局最大值。这是”路径分治”模式的核心。

---

第 5 章 LeetCode 124：二叉树中的最大路径和

5.1 题目

LeetCode 124 - Binary Tree Maximum Path Sum（困难）

二叉树中的路径被定义为一条从树中任意节点出发，沿父节点—子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其最大路径和。

输入: root = [1,2,3]
输出: 6
解释: 最优路径是 2 → 1 → 3，路径和为 2 + 1 + 3 = 6

输入: root = [-10, 9, 20, null, null, 15, 7]
输出: 42
解释: 最优路径是 15 → 20 → 7，路径和为 15 + 20 + 7 = 42

5.2 与 LeetCode 543 的关系

543 求的是”最多边数”，124 求的是”最大路径和”。两者在分治结构上完全相同，区别在于：

• 543：单臂长度 = 边的数量，恒为正（空节点返回 0）
• 124：单臂贡献 = 路径上节点值的总和，可能为负（此时不如不选这条臂）

124 的核心新难点：节点值可能是负数。如果某条臂的贡献为负，不选这条臂比选它更好。

private int maxPathSum = Integer.MIN_VALUE;  // 全局最大路径和
 
/**
 * 返回以 node 为端点向下的最大单臂贡献（向父节点延伸）
 * 如果所有路径都为负，宁可不贡献（返回 0，表示不选这条臂）
 */
private int maxGain(TreeNode node) {
    if (node == null) return 0;
 
    // 左右子树的最大贡献：如果为负则取 0（不选这条臂）
    int leftGain = Math.max(0, maxGain(node.left));
    int rightGain = Math.max(0, maxGain(node.right));
 
    // 经过 node 的最大路径和：左臂 + node 本身 + 右臂
    int priceNewPath = node.val + leftGain + rightGain;
    maxPathSum = Math.max(maxPathSum, priceNewPath);
 
    // 返回给父节点的单臂贡献：node 本身 + 左右两侧中贡献更大的那个
    return node.val + Math.max(leftGain, rightGain);
}

Math.max(0, maxGain(node.left)) 的含义：如果左子树的最大单臂贡献是负数，那么把左臂加进来只会让路径和变小，不如不选（贡献为 0，即路径在 node 处开始，不向左延伸）。

5.3 完整实现

class Solution {
    private int maxPathSum = Integer.MIN_VALUE;
 
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxPathSum;
    }
 
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
 
        // 递归：获取左右子树的最大贡献（负数贡献当 0 处理）
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0, maxGain(node.right));
 
        // 经过当前节点的最大路径和
        maxPathSum = Math.max(maxPathSum, node.val + leftGain + rightGain);
 
        // 向父节点返回的单臂贡献（只能选一侧）
        return node.val + Math.max(leftGain, rightGain);
    }
}

5.4 手工演示

以 root = [-10, 9, 20, null, null, 15, 7] 为例：

        -10
       /   \
      9     20
           /  \
          15   7

DFS 后序遍历：

1. 叶节点 9：leftGain=0, rightGain=0，路径和 = 9，返回 9
2. 叶节点 15：路径和 = 15，返回 15
3. 叶节点 7：路径和 = 7，返回 7
4. 节点 20：leftGain=max(0,15)=15, rightGain=max(0,7)=7
   • 路径和 = 20+15+7 = 42，更新 maxPathSum=42
   • 返回 20+15 = 35（向上只能选一侧，选较大的 15）
5. 节点 -10：leftGain=max(0,9)=9, rightGain=max(0,35)=35
   • 路径和 = -10+9+35 = 34，不更新 maxPathSum（42 > 34）
   • 返回 -10+35 = 25

最终 maxPathSum = 42，正确。

5.5 路径不能”分叉”的约束

在返回给父节点的单臂贡献中，我们写的是 node.val + Math.max(leftGain, rightGain)——只能选左臂或右臂之一，不能两者都选。

为什么？

一条路径是从一个节点到另一个节点的”链”，不能有分叉（Y 形）。如果在某个节点处同时向左子树和右子树延伸，那么这个节点就成了路径的”最高点”（拐点），此时这条路径在这个节点结束，不能再向上延伸。

因此，当我们计算”经过 node 的最大路径和”时，可以同时选左臂和右臂（节点是路径的最高点）；但当我们返回给父节点时，只能选一侧（因为路径还需要向上延伸，只能是一条链）。

---

第 6 章 路径分治模式的深度总结

6.1 路径分治的通用模板

这四道题的最后两道（543 和 124）都属于”路径分治”模式，其通用模板如下：

class Solution {
    private int globalResult = /* 初始值，视题意而定 */;
 
    public int solve(TreeNode root) {
        helper(root);
        return globalResult;
    }
 
    /**
     * 返回：以 node 为端点（向下延伸）的"最优单臂值"
     *      （这是 node 能向父节点贡献的最大价值）
     * 副作用：用"经过 node 的跨越路径值"更新 globalResult
     */
    private int helper(TreeNode node) {
        if (node == null) return /* 空节点的单臂值 */;
 
        int leftVal = helper(node.left);   // 左子树的最优单臂值
        int rightVal = helper(node.right); // 右子树的最优单臂值
 
        // 合并：计算经过 node 的最优路径值，更新全局结果
        globalResult = Math.max(globalResult, combine(node, leftVal, rightVal));
 
        // 向父节点返回：node 贡献的单臂值（只能选一侧延伸）
        return singleArm(node, leftVal, rightVal);
    }
}

题目	combine 逻辑	singleArm 逻辑	空节点单臂值
543（直径）	leftVal + rightVal	1 + max(leftVal, rightVal)	0
124（最大路径和）	node.val + max(0,leftVal) + max(0,rightVal)	node.val + max(0, max(leftVal, rightVal))	0

6.2 为什么要用全局变量而不是在返回值中传递

一个自然的问题：能不能不用全局变量 maxDiameter/maxPathSum，而是通过返回值传递？

不能直接这样做，因为每个节点需要向父节点返回的是”单臂值”（用于父节点计算其单臂值），而”跨越路径值”（经过该节点的最大路径）只在当前节点有意义，父节点不需要这个信息。两种信息不同，不能用同一个返回值同时传递。

可以用 pair 或自定义结构：返回 {单臂值, 经过该节点的最大路径值}，但这样代码更冗长。使用全局变量（或封装在类的成员变量里）是面试中更简洁的惯用法。

生产避坑：全局变量的初始值

• LeetCode 543：maxDiameter 初始化为 0（路径至少有 0 条边，即单节点路径）
• LeetCode 124：maxPathSum 初始化为 Integer.MIN_VALUE（因为节点值可能全为负数，最大路径和可以是负数）

初始化为 0 在 124 中是错误的——当所有节点值都是负数时，maxPathSum 会错误地返回 0。

6.3 重建分治 vs 路径分治的对比

维度	重建分治（105/106）	路径分治（543/124）
返回值含义	当前子树的根节点（TreeNode）	以当前节点为端点的最优单臂值（数值）
全局状态	不需要（答案即根节点）	需要（全局最优路径无法通过返回值传递）
信息流向	自顶向下（根节点的值指导左右子树范围） + 自底向上（构建好的子树）	自底向上（每个节点汇聚子树信息并更新全局）
关键难点	正确计算左右子树的范围下标	区分”单臂返回值”和”跨越路径更新值”

---

第 7 章 本文核心结论

1. 树的递归结构天然适合分治：根节点是天然的”分割点”，左右子树是完全独立的子问题，合并在根节点处进行。

2. 重建分治的核心：用中序序列确定左右子树范围：先序/后序告诉你根在哪里，中序告诉你左右子树各包含哪些节点。用哈希表加速查找，将 $O(n^2)$ 降到 $O(n)$。

3. 路径分治的核心：区分”单臂值”和”跨越路径值”：每个节点递归时需要向父节点报告”单臂值”（用于父节点计算自己的单臂值），同时在本地计算”跨越路径值”（用于更新全局最大）。这是树上路径类问题的通用框架。

4. 负数节点值的处理：对于 LeetCode 124，当左/右子树的单臂贡献为负时，应取 0（不延伸该方向），而不是强行加入负值。Math.max(0, gain) 是处理可选延伸的标准写法。

5. 不要以为直径或最优路径一定经过根节点：最优路径的最高点可以是任意节点，这是为什么我们需要对每个节点都计算并更新全局最大值，而不是只处理根节点。