FilesExpand file tree

 master

/

LeetCode124.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

29 lines (23 loc) · 871 Bytes

 master

/

LeetCode124.java

Top

File metadata and controls

• Code
• Blame

29 lines (23 loc) · 871 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package problems;

public class LeetCode124 {

int maxValue = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {

dfs(root);

return maxValue;

}

private int dfs(TreeNode node) {

if(node == null) {

return 0;

}

// 递归计算左右子节点的最大贡献值

// 只有在最大贡献值大于 0 时，才会选取对应子节点

int leftGain = Math.max(dfs(node.left), 0);

int rightGain = Math.max(dfs(node.right), 0);

// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值

int priceNewpath = node.val + leftGain + rightGain;

// 更新答案

maxValue = Math.max(maxValue, priceNewpath);

// 返回节点的最大贡献值

return node.val + Math.max(leftGain, rightGain);

}

}