二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径
至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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
📺 视频题解
📖 文字题解
方法一：递归
首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
具体而言，该函数的计算如下。
例如，考虑如下二叉树。
1
2
3
4
5
6
| -10
/ \
9 20
/ \
15 7
|
叶节点 $9$、$15$、$7$ 的最大贡献值分别为 $9$、$15$、$7$。
得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 $20$ 的最大贡献值等于 $20+\max(15,7)=35$，节点 $-10$ 的最大贡献值等于 $-10+\max(9,35)=25$。
上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。
根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。
<,,,,,,>
[sol1-Java]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 {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
return node.val + Math.max(leftGain, rightGain);
}
}
|
[sol1-Python3]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
| class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
priceNewpath = node.val + leftGain + rightGain
self.maxSum = max(self.maxSum, priceNewpath)
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum
|
[sol1-C++]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
29
30
| class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
int priceNewpath = node->val + leftGain + rightGain;
maxSum = max(maxSum, priceNewpath);
return node->val + max(leftGain, rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
|
[sol1-Golang]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
29
30
31
32
| func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
var maxGain func(*TreeNode) int
maxGain = func(node *TreeNode) int {
if node == nil {
return 0
}
leftGain := max(maxGain(node.Left), 0)
rightGain := max(maxGain(node.Right), 0)
priceNewPath := node.Val + leftGain + rightGain
maxSum = max(maxSum, priceNewPath)
return node.Val + max(leftGain, rightGain)
}
maxGain(root)
return maxSum
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
|
[sol1-C#]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
29
30
31
32
| public class Solution
{
int maxSum = int.MinValue;
public int MaxPathSum(TreeNode root)
{
MaxGain(root);
return maxSum;
}
int MaxGain(TreeNode node)
{
if (node == null)
{
return 0;
}
int leftGain = Math.Max(MaxGain(node.left), 0);
int rightGain = Math.Max(MaxGain(node.right), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.Max(maxSum, priceNewpath);
return node.val + Math.Max(leftGain, rightGain);
}
}
|
复杂度分析
,
,
,
,
,
,
>