力扣Hot100系列13（Java）——[二叉树]总结（下）(从前序与中序遍历序列构造二叉树，路径总和|||，二叉树的最近公共祖先，二叉树中的最大路径和)

文章目录

• 前言
• 一、从前序与中序遍历序列构造二叉树
• • 1.题目
  • 2.代码
  • 3.例子
• 二、路径总和|||
• • 1.题目
  • 2.代码
  • 3.例子
• 三、二叉树的最近公共祖先
• • 1.题目
  • 2.代码
  • 3.例子
  • • 场景1：找 p=5、q=1 的LCA
    • 场景2：找 p=5、q=4 的LCA
• 四、二叉树中的最大路径和
• • 1.题目
  • 2.代码
  • 3.例子

前言

本文记录力扣Hot100里面关于二叉树的四道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

一、从前序与中序遍历序列构造二叉树

1.题目

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

示例 1:

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

示例 2: 输入: preorder = [-1], inorder = [-1] 输出: [-1]

2.代码

步骤

private Map<Integer, Integer> indexMap;

public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
indexMap = new HashMap<Integer, Integer>();
// 构建中序值-索引映射，快速定位根节点
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
// 递归构建整棵树，初始范围为全部节点
return myBuildTree(preorder, inorder, 0, n – 1, 0, n – 1);
}

public TreeNode myBuildTree(int[] preorder, int[] inorder,
int preorder_left, int preorder_right,
int inorder_left, int inorder_right) {
// 递归终止：无节点可构建
if (preorder_left > preorder_right) {
return null;
}

// 前序首元素为当前根节点，查找其在中序中的位置
int preorder_root = preorder_left;
int inorder_root = indexMap.get(preorder[preorder_root]);

TreeNode root = new TreeNode(preorder[preorder_root]);
// 计算左子树节点数，用于划分前序遍历范围
int size_left_subtree = inorder_root – inorder_left;

// 递归构建左子树
root.left = myBuildTree(preorder, inorder,
preorder_left + 1, preorder_left + size_left_subtree,
inorder_left, inorder_root – 1);

// 递归构建右子树
root.right = myBuildTree(preorder, inorder,
preorder_left + size_left_subtree + 1, preorder_right,
inorder_root + 1, inorder_right);

return root;
}

3.例子

示例 首先定义一个简单的二叉树：

3
/ \\
9 20
/ \\
15 7

对应的遍历结果：

• 前序遍历 (preorder)：[3, 9, 20, 15, 7]（根 → 左 → 右）
• 中序遍历 (inorder)：[9, 3, 15, 20, 7]（左 → 根 → 右）

1. 初始化哈希表 代码首先遍历中序数组，构建「数值→索引」的映射：

2. 第一次调用 myBuildTree（构建整棵树） 传入参数：

• preorder_left=0, preorder_right=4
• inorder_left=0, inorder_right=4

步骤1：前序根节点索引 preorder_root=0，对应数值 3。 步骤2：查哈希表，3 在中序的索引 inorder_root=1。 步骤3：创建根节点 TreeNode(3)。 步骤4：左子树节点数 size_left_subtree = 1 – 0 = 1（中序根左边只有1个元素）。

步骤5：递归构建左子树（参数）：

• pre_left+1=1, pre_left+size=0+1=1 → 前序范围 [1,1]（对应数值9）
• in_left=0, in_root-1=0 → 中序范围 [0,0]（对应数值9）

步骤6：递归构建右子树（参数）：

• pre_left+size+1=0+1+1=2, pre_right=4 → 前序范围 [2,4]（对应数值20,15,7）
• in_root+1=2, in_right=4 → 中序范围 [2,4]（对应数值15,20,7）

3. 递归构建左子树（根节点3的左孩子） 传入参数：

• preorder_left=1, preorder_right=1
• inorder_left=0, inorder_right=0

步骤1：前序根节点索引 preorder_root=1，对应数值 9。 步骤2：查哈希表，9 在中序的索引 inorder_root=0。 步骤3：创建节点 TreeNode(9)。 步骤4：左子树节点数 size_left_subtree = 0 – 0 = 0。

步骤5：递归构建左子树（参数 [2,1]）→ 左边界>右边界，返回 null。 步骤6：递归构建右子树（参数 [2,1]）→ 返回 null。

最终返回节点 9，作为根节点3的左孩子。

4. 递归构建右子树（根节点3的右孩子） 传入参数：

• preorder_left=2, preorder_right=4
• inorder_left=2, inorder_right=4

步骤1：前序根节点索引 preorder_root=2，对应数值 20。 步骤2：查哈希表，20 在中序的索引 inorder_root=3。 步骤3：创建节点 TreeNode(20)。 步骤4：左子树节点数 size_left_subtree = 3 – 2 = 1（中序根左边有1个元素）。

步骤5：递归构建左子树（参数）：

• pre_left+1=3, pre_left+size=2+1=3 → 前序范围 [3,3]（对应数值15）
• in_left=2, in_root-1=2 → 中序范围 [2,2]（对应数值15）

步骤6：递归构建右子树（参数）：

• pre_left+size+1=2+1+1=4, pre_right=4 → 前序范围 [4,4]（对应数值7）
• in_root+1=4, in_right=4 → 中序范围 [4,4]（对应数值7）

5. 递归构建20的左孩子（15）和右孩子（7）

• 构建15：参数范围均为单元素，创建 TreeNode(15)，左右孩子均为 null，返回作为20的左孩子。
• 构建7：参数范围均为单元素，创建 TreeNode(7)，左右孩子均为 null，返回作为20的右孩子。

3
/ \\
9 20
/ \\
15 7

二、路径总和|||

1.题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。

示例 2： 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3

2.代码

步骤

public int pathSum(TreeNode root, int targetSum) {
// 前缀和->出现次数，快速匹配目标路径
Map<Long, Integer> prefix = new HashMap<Long, Integer>();
// 初始化前缀和0，处理根节点开始的路径
prefix.put(0L, 1);
return dfs(root, prefix, 0, targetSum);
}

public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
if (root == null) {
return 0;
}

int ret = 0;
curr += root.val; // 累计当前节点的前缀和

// 统计以当前节点为终点的符合条件路径数
ret = prefix.getOrDefault(curr – targetSum, 0);
// 记录当前前缀和，供子节点查询
prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

// 递归累加左右子树的符合条件路径数
ret += dfs(root.left, prefix, curr, targetSum);
ret += dfs(root.right, prefix, curr, targetSum);

// 回溯：恢复前缀和计数，避免影响其他分支
prefix.put(curr, prefix.getOrDefault(curr, 0) – 1);

return ret;
}

3.例子

示例 首先定义一棵二叉树，并指定目标和 targetSum = 8：

10
/ \\
5 -3
/ \\ \\
3 2 11
/ \\ \\
3 -2 1

我们要统计这棵树中路径和为8的所有路径（路径定义：从任意节点出发，沿父节点→子节点方向，连续向下的节点序列）。 先给出最终答案：符合条件的路径有3条：

核心概念先明确

• 前缀和：从根节点到当前节点的路径上所有节点值的累加和。
• 核心公式：若「当前前缀和 – 目标和 = 某个祖先的前缀和」，则这两个节点之间的路径和等于目标和。
• 回溯：遍历完一个节点的左右子树后，要把该节点的前缀和从哈希表中“撤回”，避免影响其他分支的计算。

（按DFS遍历顺序）

初始化：

• prefix 哈希表初始值：{0:1}（前缀和为0的情况出现1次）
• 调用 dfs(root=10, prefix={0:1}, curr=0, targetSum=8)

第一步：处理根节点 10

// 递归进入dfs(10, {0:1}, 0, 8)
curr = 0 + 10 = 10;
// 步骤1：找curr – targetSum = 10-8=2 → prefix中无2，ret=0
ret = prefix.getOrDefault(2, 0) = 0;
// 步骤2：存入当前前缀和10 → prefix变为 {0:1, 10:1}
prefix.put(10, 1);
// 步骤3：递归处理左孩子5
ret += dfs(5, {0:1,10:1}, 10, 8);
// 步骤4：递归处理右孩子-3（等左子树处理完后执行）
ret += dfs(–3, {0:1,10:1}, 10, 8);
// 步骤5：回溯 → prefix.put(10, 0)（后续会被其他分支覆盖，暂不细究）

第二步：处理节点 5（10的左孩子）

// 递归进入dfs(5, {0:1,10:1}, 10, 8)
curr = 10 + 5 = 15;
// 步骤1：找curr – targetSum =15-8=7 → prefix中无7，ret=0
ret = prefix.getOrDefault(7, 0) = 0;
// 步骤2：存入当前前缀和15 → prefix变为 {0:1, 10:1, 15:1}
prefix.put(15, 1);
// 步骤3：递归处理左孩子3
ret += dfs(3, {0:1,10:1,15:1}, 15, 8);
// 步骤4：递归处理右孩子2
ret += dfs(2, {0:1,10:1,15:1}, 15, 8);
// 步骤5：回溯 → prefix.put(15, 0)

第三步：处理节点 3（5的左孩子）

// 递归进入dfs(3, {0:1,10:1,15:1}, 15, 8)
curr = 15 + 3 = 18;
// 步骤1：找curr – targetSum =18-8=10 → prefix中有10，次数是1 → ret=1
ret = prefix.getOrDefault(10, 0) = 1; // 这是第一条符合条件的路径：5→3
// 步骤2：存入当前前缀和18 → prefix变为 {0:1, 10:1, 15:1, 18:1}
prefix.put(18, 1);
// 步骤3：递归处理左孩子3 → 返回0（无符合路径）
ret += dfs(3, ...) = 0;
// 步骤4：递归处理右孩子-2 → 返回0（无符合路径）
ret += dfs(–2, ...) = 0;
// 步骤5：回溯 → prefix.put(18, 0)
// 返回ret=1（给父节点5）

第四步：处理节点 2（5的右孩子）

// 递归进入dfs(2, {0:1,10:1,15:1}, 15, 8)
curr = 15 + 2 = 17;
// 步骤1：找curr – targetSum =17-8=9 → prefix中无9，ret=0
ret = prefix.getOrDefault(9, 0) = 0;
// 步骤2：存入当前前缀和17 → prefix变为 {0:1, 10:1, 15:1, 17:1}
prefix.put(17, 1);
// 步骤3：递归处理右孩子1
ret += dfs(1, ...);
// 步骤4：无左孩子，加0
// 步骤5：回溯 → prefix.put(17, 0)

子步骤：处理节点1（2的右孩子）

// 递归进入dfs(1, {0:1,10:1,15:1,17:1}, 17, 8)
curr = 17 + 1 = 18;
// 步骤1：找curr – targetSum =18-8=10 → prefix中有10，次数是1 → ret=1
ret = prefix.getOrDefault(10, 0) = 1; // 这是第二条符合条件的路径：5→2→1
// 步骤2：存入18 → prefix加{18:1}
// 步骤3/4：无孩子，加0
// 步骤5：回溯 → 18的次数减1
// 返回ret=1（给父节点2）

所以节点2最终返回 ret=0+1=1（给父节点5）。

第五步：回到节点5的计算 节点5的 ret = 0（初始） + 1（左孩子3） + 1（右孩子2） = 2，返回给根节点10。

第六步：处理节点 -3（10的右孩子）

// 递归进入dfs(-3, {0:1,10:1}, 10, 8)
curr = 10 + (–3) = 7;
// 步骤1：找curr – targetSum =7-8=-1 → prefix中无-1，ret=0
ret = prefix.getOrDefault(–1, 0) = 0;
// 步骤2：存入当前前缀和7 → prefix变为 {0:1, 10:1, 7:1}
prefix.put(7, 1);
// 步骤3：无左孩子，加0
// 步骤4：递归处理右孩子11
ret += dfs(11, ...);
// 步骤5：回溯 → prefix.put(7, 0)

子步骤：处理节点11（-3的右孩子）

// 递归进入dfs(11, {0:1,10:1,7:1}, 7, 8)
curr = 7 + 11 = 18;
// 步骤1：找curr – targetSum =18-8=10 → prefix中有10，次数是1 → ret=1
ret = prefix.getOrDefault(10, 0) = 1; // 这是第三条符合条件的路径：-3→11
// 步骤2：存入18 → prefix加{18:1}
// 步骤3/4：无孩子，加0
// 步骤5：回溯 → 18的次数减1
// 返回ret=1（给父节点-3）

所以节点-3最终返回 ret=0+1=1，返回给根节点10。

第七步：回到根节点10的计算 根节点10的 ret = 0（初始） + 2（左孩子5） + 1（右孩子-3） = 3，这就是最终结果。

三、二叉树的最近公共祖先

1.题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大 （一个节点也可以是它自己的祖先）。”

示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3： 输入：root = [1,2], p = 1, q = 2 输出：1

2.代码

步骤

class Solution {
private TreeNode ans;

public Solution() {
this.ans = null;
}

// 后序遍历判断子树是否含p/q，同时定位LCA
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;

boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);

// 满足条件则当前节点为LCA：1.左右子树各含一个目标 2.当前是目标且子树含另一个
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}

// 返回当前节点/子树是否包含p或q
return lson || rson || (root.val == p.val || root.val == q.val);
}

// 入口：调用DFS查找并返回LCA
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}

3.例子

示例 首先定义一棵二叉树（LeetCode 236题经典示例）：

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

我们要找两个节点的最近公共祖先，分两种典型场景演示：

先明确规则：最近公共祖先是两个节点的最深公共祖先节点，要么是“左右子树各含一个目标节点”，要么是“自身是一个目标节点且子树含另一个”。

场景1：找 p=5、q=1 的LCA

步骤（DFS后序遍历，从根节点3开始）

// 调用入口：lowestCommonAncestor(root=3, p=5, q=1) → 执行dfs(3,5,1)

第一步：执行 dfs(3,5,1)

// 递归终止：root≠null，继续
// 第一步：查左子树（节点5）
boolean lson = dfs(5,5,1);
// 第二步：查右子树（节点1）
boolean rson = dfs(1,5,1);
// 第三步：判定LCA条件
// lson=true（左子树含5），rson=true（右子树含1）→ 满足 (lson&&rson)
ans = 3; // 找到LCA，赋值为3
// 返回：true（左/右子树含5或1）
return true;

第二步：拆解 dfs(5,5,1)（根3的左子树）

// root=5≠null，继续
// 第一步：查左子树（节点6）
boolean lson = dfs(6,5,1); // → 返回false（6的子树无5/1）
// 第二步：查右子树（节点2）
boolean rson = dfs(2,5,1); // → 返回false（2的子树无5/1）
// 第三步：判定LCA条件
// (false&&false) 不满足；但 (root.val=5 == p.val=5) 且 (false||false) → 不满足
ans 仍为null；
// 返回：false||false||(5==5||5==1) → true（自身是5，包含目标节点）
return true;

• 其中 dfs(6,5,1)：root=6≠null，查左/右子树（均为null，返回false），判定条件不满足，返回 false；
• 其中 dfs(2,5,1)：root=2≠null，查左（7）、右（4）子树（均返回false），判定条件不满足，返回 false。

第三步：拆解 dfs(1,5,1)（根3的右子树）

// root=1≠null，继续
// 第一步：查左子树（节点0）
boolean lson = dfs(0,5,1); // → 返回false（0的子树无5/1）
// 第二步：查右子树（节点8）
boolean rson = dfs(8,5,1); // → 返回false（8的子树无5/1）
// 第三步：判定LCA条件
// (false&&false) 不满足；但 (root.val=1 == q.val=1) 且 (false||false) → 不满足
ans 仍为null；
// 返回：false||false||(1==5||1==1) → true（自身是1，包含目标节点）
return true;

• 其中 dfs(0,5,1)、dfs(8,5,1) 均返回 false（逻辑同dfs(6,5,1)）。

最终结果 dfs(3,5,1) 执行完成后，ans=3，即5和1的最近公共祖先是3。

场景2：找 p=5、q=4 的LCA

步骤（核心看节点5的判定逻辑）

// 调用入口：lowestCommonAncestor(root=3, p=5, q=4) → 执行dfs(3,5,4)

第一步：执行 dfs(3,5,4)

// 查左子树（节点5）
boolean lson = dfs(5,5,4); // → 返回true
// 查右子树（节点1）
boolean rson = dfs(1,5,4); // → 返回false
// 判定LCA条件：(true&&false) 不满足；(3==5||3==4) 也不满足 → ans仍为null
// 返回：true||false||false → true
return true;

第二步：拆解 dfs(5,5,4）

// root=5≠null，继续
// 第一步：查左子树（节点6）
boolean lson = dfs(6,5,4); // → 返回false
// 第二步：查右子树（节点2）
boolean rson = dfs(2,5,4); // → 返回true（2的子树含4）
// 第三步：判定LCA条件
// (false&&true) 不满足；但 (root.val=5 == p.val=5) 且 (false||true) → 满足！
ans = 5; // 找到LCA，赋值为5
// 返回：false||true||(5==5||5==4) → true
return true;

第三步：拆解 dfs(2,5,4)（节点5的右子树）

// root=2≠null，继续
// 第一步：查左子树（节点7）→ 返回false
// 第二步：查右子树（节点4）→ 返回true
boolean rson = dfs(4,5,4);
// 第三步：判定LCA条件：不满足（无赋值）
// 返回：false||true||false → true
return true;

第四步：拆解 dfs(4,5,4)（节点2的右子树）

// root=4≠null，继续
// 查左/右子树（均为null，返回false）
// 判定LCA条件：不满足
// 返回：false||false||(4==5||4==4) → true（自身是4，包含目标节点）
return true;

最终结果 dfs(3,5,4) 执行完成后，ans=5，即5和4的最近公共祖先是5。

四、二叉树中的最大路径和

1.题目

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

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

示例 2：

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

2.代码

步骤

class Solution {
// 存储最大路径和，初始为整型最小值（兼容全负数场景）
int res = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}

// 返回以当前节点为起点的最大单边路径和
int dfs(TreeNode node){
if(node == null) return 0;

// 左子树单边和（负数则舍弃，取0）
int leftMax = Math.max(0, dfs(node.left));
// 右子树单边和（负数则舍弃，取0）
int rightMax = Math.max(0, dfs(node.right));

// 更新全局最大路径和（当前节点为顶点的完整路径）
res = Math.max(res, leftMax + rightMax + node.val);

// 返回单边路径和（仅选左/右中较大的方向）
return node.val + Math.max(leftMax, rightMax);
}
}

3.例子

示例 首先定义一棵二叉树（包含正数、负数，能覆盖核心场景）：

-10
/ \\
9 20
/ \\
15 7

我们要找这棵树的最大路径和，先给出最终答案：15 + 20 + 7 = 42。

核心概念先明确

• 最大单边路径和：以当前节点为起点，向子节点方向延伸的最大路径和（只能选左或右一个方向），是递归的返回值，供父节点计算使用。
• 完整路径和：以当前节点为顶点，连接左右子树的路径和（左+当前+右），用于更新全局最大路径和（res）。

步骤拆解（按DFS递归顺序） 初始化：res = Integer.MIN_VALUE（即 -2147483648），调用 maxPathSum(root=-10) → 执行 dfs(-10)。

第一步：递归处理叶子节点 9（-10的左孩子）

// 执行 dfs(9)
// 递归终止：9的左、右子节点都是null → dfs(null)=0
int leftMax = Math.max(0, 0) = 0;
int rightMax = Math.max(0, 0) = 0;

// 计算完整路径和：0 + 0 + 9 = 9 → 更新res为 max(-2147483648, 9) = 9
res = 9;

// 返回单边路径和：9 + max(0,0) = 9
return 9;

第二步：递归处理叶子节点 15（20的左孩子）

// 执行 dfs(15)
// 左、右子节点都是null → leftMax=0，rightMax=0

// 完整路径和：0+0+15=15 → 更新res为 max(9,15)=15
res = 15;

// 返回单边路径和：15 + 0 =15
return 15;

第三步：递归处理叶子节点 7（20的右孩子）

// 执行 dfs(7)
// 左、右子节点都是null → leftMax=0，rightMax=0

// 完整路径和：0+0+7=7 → res仍为 max(15,7)=15
res = 15;

// 返回单边路径和：7 + 0 =7
return 7;

第四步：递归处理节点 20（-10的右孩子）

// 执行 dfs(20)
// 第一步：递归左子树15 → 返回15 → leftMax = Math.max(0,15)=15
// 第二步：递归右子树7 → 返回7 → rightMax = Math.max(0,7)=7

// 第三步：计算完整路径和：15 + 7 + 20 = 42 → 更新res为 max(15,42)=42
res = 42;

// 第四步：返回单边路径和：20 + max(15,7) = 20+15=35
return 35;

第五步：递归处理根节点 -10

// 执行 dfs(-10)
// 第一步：递归左子树9 → 返回9 → leftMax = Math.max(0,9)=9
// 第二步：递归右子树20 → 返回35 → rightMax = Math.max(0,35)=35

// 第三步：计算完整路径和：9 + 35 + (-10) = 34 → res仍为 max(42,34)=42
res = 42;

// 第四步：返回单边路径和：-10 + max(9,35) = -10+35=25
return 25;

最终结果 maxPathSum 方法返回 res=42，即这棵树的最大路径和是42（对应路径：15→20→7）。

补充场景：包含负数的情况 例：

-10
/ \\
-9 20
/ \\
15 7

处理节点-9时：

// dfs(-9)
leftMax=0，rightMax=0
完整路径和：0+0+(–9) = –9 → res更新为 max(–2147483648, –9) = –9
返回单边路径和：–9 + 0 = –9

处理根节点-10时：

leftMax = Math.max(0, –9) = 0; // 左子树返回负数，舍弃，取0
rightMax = 35;
完整路径和：0 + 35 + (–10) = 25 → res最终为 max(42,25)=42

可以看到，代码会自动舍弃负数贡献的子树，保证路径和最大。

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！