78.二叉树中的最大路径和
题目
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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
提示：
- 树中节点数目范围是 [1, 3 * 104]
- -1000 <= Node.val <= 1000
思路
这里可以是任意路径，但是不能重复经过同一个节点。
所以如果选了左、根、右这三个节点，那就没法再往上去走了，因为再往上又要经过根节点。
所以对于每个节点，需要考虑两种不同的问题:
-
问题一: 经过这个节点的最大路径和事多少？
也就是 = 左边贡献 + 当前节点值 + 右边贡献
-
问题二: 这个节点能向上贡献多少?
也就是 = 当前节点值 + max(左边贡献， 右边贡献) 只能选一边，因为路径不能拐弯后再往上走
-10
/ \
9 20
/ \
15 7
处理叶子节点 9：
经过9的最大路径 = 9，更新全局答案 = 9
向上贡献 = max(9, 0) = 9（负数就贡献0，相当于不选这条路）
处理叶子节点 15：
经过15的最大路径 = 15，更新全局答案 = 15
向上贡献 = 15
处理叶子节点 7：
经过7的最大路径 = 7，更新全局答案 = 15
向上贡献 = 7
处理节点 20：
左边贡献 = 15，右边贡献 = 7
经过20的最大路径 = 15 + 20 + 7 = 42，更新全局答案 = 42
向上贡献 = 20 + max(15, 7) = 35
处理根节点 -10：
左边贡献 = max(9, 0) = 9，右边贡献 = 35
经过-10的最大路径 = 9 + (-10) + 35 = 34，全局答案仍是 42
向上贡献 = -10 + max(9, 35) = 25（但根节点不需要向上贡献）
最终答案 = 42 ✅
class Solution {
private var maxSum = Int.MIN_VALUE
fun maxPathSum(root: TreeNode?): Int {
dfs(root)
return maxSum
}
// 返回值：当前节点能向上贡献的最大路径和
private fun dfs(node: TreeNode?): Int {
if (node == null) return 0
// 左右子树向上的贡献，负数就取 0（相当于不选那条路）
val leftGain = maxOf(dfs(node.left), 0)
val rightGain = maxOf(dfs(node.right), 0)
// 以当前节点为"最高点"的路径和（可以拐弯）
val pathThroughNode = node.`val` + leftGain + rightGain
// 更新全局最大值
maxSum = maxOf(maxSum, pathThroughNode)
// 向上只能贡献一边（不能拐弯）
return node.`val` + maxOf(leftGain, rightGain)
}
}
复杂度
- 时间复杂度: O(n)，每个节点访问一次
- 空间复杂度: O(h)，递归栈深度，h为树的高度
- 邮箱 ：charon.chui@gmail.com
- Good Luck!