当前位置：首页 > news >正文

算法：二叉树最大路径和

news 2026/5/12 2:56:24

核心解题思路

要理解这个算法，你需要明白二叉树中的任何一个节点在计算路径时，其实扮演了两个不同的角色：

1. 对“上级”（父节点）的角色：只能提供一条腿

当一个节点（比如 root）向它的父节点汇报工作时，它不能把“左+根+右”这个像拱桥一样的路径汇报上去。因为路径不能分叉，一条路径要想继续向上延伸，只能选择左边或者右边的一条路。

汇报值= root->val + max(左子树能提供的最大单边路径, 右子树能提供的最大单边路径)。

2. 对“全局答案”的角色：可以是路径的最高点（拐点）

一条路径可以在当前节点“拐弯”。也就是说，路径可以是左子树 -> 当前节点 -> 右子树。

当前节点为拐点的最大路径和= 左子树最大贡献 + 右子树最大贡献 + root->val。

我们需要每遍历到一个节点，就计算一下以它为“拐点”的路径和是否比当前的全局最大值 ans 还要大。如果是，就更新 ans。

完整代码：

class Solution { public: int maxPathSum(TreeNode* root) { int ans = INT_MIN; // 初始化为一个最小值，防止题目全是负数节点时出错 dfs(root, ans); // 开始递归 return ans; // 返回最终找到的全局最大路径和 } // 注意这里 ans 是引用传递 (int &ans)，这样递归中修改的都是同一个变量 int dfs(TreeNode *root, int &ans) { // 1. 递归终止条件（Base Case） // 如果节点为空，它对路径的贡献就是 0 if (root == nullptr) return 0; // 2. 递归计算左右子树的“最大贡献值” // 核心逻辑：max(0, ...) 是精华所在！ // 如果子树计算出的路径和是负数（比如 -10），那我们不如不选那条路（即贡献为 0）。 // 这相当于“剪枝”，把负贡献的尾巴剪掉。 int left = max(0, dfs(root->left, ans)); int right = max(0, dfs(root->right, ans)); // 3. 计算“单边最大路径”（用于返回给父节点） // temp 代表：如果父节点想连我，我能提供的最大值。 // 我只能带上我左右孩子中较大的那一个（或者都不带，如果都是0）。 int temp = max(left, right) + root->val; // 4. 更新全局最大值（ans） // 这里原作者写了两行更新，其实逻辑涵盖了两种情况： // 第一行：更新单边路径的情况（比如路径只到当前节点为止，或者只连一边） ans = max(ans, temp); // 第二行：更新“拱桥”情况（最关键的一步） // 路径形态：左孩子 -> 当前节点 -> 右孩子 // 这代表路径在当前节点这里“拐弯”了，不再向父节点延伸。 ans = max(ans, left + right + root->val); // 5. 返回值 // 注意！这里必须返回 temp。 // 因为 dfs 函数的定义是“返回该节点能给父节点提供的最大单边路径”。 // 你不能返回“左+根+右”，因为那是一条死路（两头都堵住了），不能再连父节点了。 return temp; } };

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

步骤演示：

处理节点 2 (左子叶):
- left, right 都是 0 (因为无子节点)。
- temp (汇报给父节点) = $0 + 0 + 2 = 2$。
- 更新 ans：此时 ans 可能是 2 (视初始化和遍历顺序而定)。
- 返回 2。
处理节点 3 (右子叶):
- left, right 都是 0。
- temp (汇报给父节点) = $0 + 0 + 3 = 3$。
- 更新 ans：ans 更新为 3。
- 返回 3。
处理节点 1 (根节点):
- left = 2 (来自节点 2 的返回值)。
- right = 3 (来自节点 3 的返回值)。
- 计算拱桥路径 (拐点路径):$left + right + root->val = 2 + 3 + 1 = 6$。
- 更新 ans：ans 变为6。
- 计算返回值 (temp):max(2, 3) + 1 = 4 (这意味着如果 1 还有父节点，它会汇报 4)。