Hot 100 --- 二叉树中的最大路径和

本文概览：本文以LeetCode题目"二叉树中的最大路径和"为例，讲解"拐点"视角的思路——每个节点作为拐点更新全局最大值，同时只传单边最大路径给父节点

一、题目

二、题目分析

题目要求：给定一棵二叉树，找到路径和最大的路径。路径可以从任意节点出发，到任意节点结束，但必须沿着父子关系往下走，不能分叉

难点在于二叉树有左右两条分支，一条路径可能只走左子树，可能只走右子树，也可能经过某个节点后同时走左右两棵子树

这题的示例有一点误导性：它写了"15 → 20 → 7"这样的箭头，容易让人先入为主地以为路径有方向顺序，从而联想到左→根→右的中序遍历。但实际上方向无所谓——题目完全可以写成"20 → 15 → 7"或"7 → 20 → 15"，只要两个节点之间有连线，它们就是连通的，顺序不重要。所以不要被箭头误导成某种特定遍历方式

思路概览

Java 实现代码如下

classSolution{privateintmaxSum=Integer.MIN_VALUE;publicintmaxPathSum(TreeNoderoot){dfs(root);returnmaxSum;}privateintdfs(TreeNodenode){if(node==null){return0;}// 递归计算左子树的最大路径和intleft=Math.max(0,dfs(node.left));// 递归计算右子树的最大路径和intright=Math.max(0,dfs(node.right));// 更新最大路径和maxSum=Math.max(maxSum,node.val+left+right);// 返回当前节点的最大路径和returnnode.val+Math.max(left,right);}}

思路简要说明

核心是"拐点视角"：把每个节点看作一条路径的最高点（拐点），路径从这个节点的左子树上来，经过这个节点，再下到右子树。每个节点做两件事：

1. 作为拐点更新全局最大值：以当前节点为拐点的路径和 =node.val + 左子树最大路径 + 右子树最大路径，和maxSum比，大就更新
2. 作为子路径传给父节点：父节点需要知道当前节点这条路径可不可以走，只要是正数就有可能对父节点的路径有增益、有可能更新最大值，所以要把当前节点的单边最大路径返回给父节点（具体为什么返回单边，下面详解说）

另一个关键点：子树最大路径如果小于 0，就当 0 处理（Math.max(0, dfs(...))），因为负数路径只会拉低总和，不如不要这条子树

三、思路详解

第一步：为什么要找"拐点"？

先看题目给的例子：

输入：[-10, 9, 20, null, null, 15, 7] 输出：42 解释：最优路径是 15 -> 20 -> 7

对应二叉树：

-10 / \ 9 20 / \ 15 7

如果从整体去看，这条路径15 → 20 → 7似乎很难找——二叉树有左右两条分支，路径可能只走一边，也可能两边都走，到底怎么组合才能最大？

换个角度想：这条路径有一个特点——它经过节点 20，而 20 是这条路径在树里的最高点。路径从 20 的左子树（15）延伸过来，经过 20，再延伸到右子树（7）

-10 / \ 9 20 ← 20 是这条路径的最高点 / \ 15 7

任何一条路径在二叉树里都有且只有一个这样的最高点——从这个节点开始，路径分别往左右两边延伸下去。我们把这个节点叫做"拐点"

既然每条路径都有一个拐点，那找最大路径和就转化成了：对每个节点，算出以它为拐点的路径和，取最大值就是答案。这样就把一个整体问题拆成了对每个节点的局部问题

第二步：作为拐点——更新全局最大值

对于任意一个节点，如果它是某条路径的拐点，那么这条路径的形态一定是：

左子树的某条路径 ← 当前节点 → 右子树的某条路径

要使这条路径最大，就要让左右两边的路径都最大。所以以当前节点为拐点的最大路径和 =node.val + 左子树最大路径 + 右子树最大路径

20 / \ 15 7 以 20 为拐点的路径和 = 20 + 15 + 7 = 42

这就是maxSum = Math.max(maxSum, node.val + left + right)这行的含义——用当前节点作为拐点尝试更新全局最大值

第三步：作为子路径——传给父节点什么？

当前节点算完拐点路径和之后，还要返回一个值给父节点。这里要理解一件事：父节点也是拐点，它也在算自己的拐点路径和

比如节点 20 给父节点 -10 返回时，-10 也在算"以 -10 为拐点的路径和"。-10 作为拐点，它的路径形态是9 ← -10 → 20 这边。注意 -10 的右边只能接 20 的某一条路径——要么是 20→15 这条，要么是 20→7 这条，不能两条都接，因为路径不能分叉

-10 ← -10 是拐点，右边只能接 20 的一条路径 / \ 9 20 ← 20 返回给 -10 的是单边最大路径 / \ 15 7

所以 20 返回给 -10 的值，应该是20 + max(15, 7)= 35，即走左子树和走右子树中较大的那条

这就是return node.val + Math.max(left, right)的含义——返回单边最大路径和给父节点

为什么只要是正数都要返回：因为父节点作为拐点时，它的路径和 =父.val + 左 + 右。只要当前节点返回的值是正数，加到父节点上就能让父节点的拐点路径和更大，有更新最大值的可能。所以正数路径对父节点来说是有益的，必须返回

第四步：负数路径当 0 处理

代码里有个细节：int left = Math.max(0, dfs(node.left))

为什么要和 0 比较？因为子树的最大路径和可能是负数。如果左子树整体都是负数，那把左子树加进来只会拉低总和，不如不要这条子树

5 / -3 / \ -1 -2 5 的左子树最大路径 = -3 + (-1) 或 -3 + (-2) 都是负数 如果加进来：5 + (-3) = 2 如果不要：5 + 0 = 5 ← 更大

所以子树返回值小于 0 时，直接当 0 处理，相当于"放弃这条子树"

对于拐点更新也是同理：如果左右子树都是负数，left=0, right=0，拐点路径和 =node.val + 0 + 0 = node.val，也就是只要这个节点自己

第五步：完整执行过程

以这棵树为例：

-10 / \ 9 20 / \ 15 7

初始：maxSum = Integer.MIN_VALUE

访问节点 9（当前路径：-10→9）

• 左子树 null → left = 0
• 右子树 null → right = 0
• 拐点更新：maxSum = max(MIN, 9 + 0 + 0) = 9
• 返回单边：9 + max(0, 0) = 9

访问节点 15（当前路径：-10→20→15）

• 左子树 null → left = 0
• 右子树 null → right = 0
• 拐点更新：maxSum = max(9, 15 + 0 + 0) = 15
• 返回单边：15 + max(0, 0) = 15

访问节点 7（当前路径：-10→20→7）

• 左子树 null → left = 0
• 右子树 null → right = 0
• 拐点更新：maxSum = max(15, 7 + 0 + 0) = 15
• 返回单边：7 + max(0, 0) = 7

访问节点 20（当前路径：-10→20）

• left = max(0, 15) = 15
• right = max(0, 7) = 7
• 拐点更新：maxSum = max(15, 20 + 15 + 7) = 42 ← 找到最大值
• 返回单边：20 + max(15, 7) = 35

访问节点 -10（当前路径：-10）

• left = max(0, 9) = 9
• right = max(0, 35) = 35
• 拐点更新：maxSum = max(42, -10 + 9 + 35) = 42（-10 拉低了，没有更新）
• 返回单边：-10 + max(9, 35) = 25

最终结果：maxSum = 42，对应路径 15 → 20 → 7

关键点：节点 20 作为拐点时算出了 42，但传给父节点 -10 的只有单边 35（20+15）。因为如果 -10 是拐点，它另一边只能留给自己，不能让 20 两边都走

第六步：和最大子数组和的思路对比

这道题和最大子数组和的思路本质上是相通的：

核心都是：不关注整条路径，只关注当前位置的关键状态，然后每一步都尝试更新全局最大值

复杂度分析

• 时间复杂度：O(n)，每个节点遍历一次
• 空间复杂度：O(h)，递归栈深度等于树的高度，最坏情况 O(n)