-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode124.java
73 lines (64 loc) · 2.06 KB
/
Leetcode124.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package tree;
import tree.treenode.TreeNode;
/**
* @BelongsProject: LeetCode
* @BelongsPackage: tree
* @Author: elvis
* @CreateTime: 2020-08-19 14:29
* @Description: 二叉树中的最大路径和
* 给定一个非空二叉树,返回其最大路径和。
*
* 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
*
* 示例 1:
*
* 输入: [1,2,3]
*
* 1
* / \
* 2 3
*
* 输出: 6
* 示例 2:
*
* 输入: [-10,9,20,null,null,15,7]
*
* -10
* / \
* 9 20
* / \
* 15 7
*
* 输出: 42
*/
public class Leetcode124 {
/**
* 首先,考虑实现一个简化的函数 maxGain(node),该函数计算二叉树中的一个节点的最大贡献值,具体而言,就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径,使得该路径上的节点值之和最大。
*
* 具体而言,该函数的计算如下。
*
* 空节点的最大贡献值等于 00。
*
* 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和(对于叶节点而言,最大贡献值等于节点值)
*/
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 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);
}
}