📝 题目描述

题目链接：二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

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

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

示例：

示例 1：

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

示例 2：

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

提示：

  • 树中节点数目范围是 [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000

💡 解题思路

方法一：递归

首先不要被“路径还能横着走”吓到。

思考：参考“最大子数组和”，对于一个节点，如何计算它的单边最大贡献值？

我们思考从上到下单走一条路的情况，也即只选择它的左右子树其中一条往下走的情况。它的最大贡献值 gain 很显然：先分别计算它的左右子树的最大贡献值 leftGain 和 rightGain，然后如果有大于 0 的，那么 gain = node -> val + max(leftGain, rightGain)；如果左右子树的贡献值都小于 0，那么 gain = node -> val。

思考：如何实现“路径还能横着走”？

也就是如何利用起来上面计算的单边最大贡献值。其实很简单，在计算向上传递的“单边最大贡献”时，顺手把“以当前节点为最高点的最大路径和”给算出来，并更新全局变量即可。
什么是“以当前节点为最高点的最大路径和”？其实就是加起来“node->val + leftGain + rightGain”，这样就实现了“横着走的路径”。

🔧 代码实现

1、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    int maxSum = INT_MIN; // 全局最大路径和

    // 返回值：以当前 node 为起点的单边最大贡献值
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        
        // 1. 递归计算左右子树的最大贡献值，如果贡献值小于 0 则舍弃
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 2. 算最高点：判断以当前节点为最高点的路径和，是否能刷新全局最大值
        // 内部路径和 = 当前节点值 + 左子树贡献 + 右子树贡献
        int priceNewpath = node->val + leftGain + rightGain;
        maxSum = max(maxSum, priceNewpath);

        // 3. 向上返回：告诉父节点，当前节点能提供的最大单边贡献
        // 规则是：只能选左子树或右子树中较大的一个分支走，或者只走当前节点（当左右都为 0 时）
        return node->val + max(leftGain, rightGain);
    }

public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

📊 复杂度分析

1、递归

  • 时间复杂度：O(N)O(N)，其中 N 是二叉树中的节点个数，对每个节点访问不超过 2 次。
  • 空间复杂度：O(N)O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

🎯 总结

  • 核心思想：想到“以当前节点为最高点的路径和”意味着什么。