1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class BinaryTreeMaximumPathSum {
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
helper(max, root);
return max[0];
}
private int helper(int[] max, TreeNode root) {
if (root == null) {
return 0;
}
int left = helper(max, root.left);
int right = helper(max, root.right);
int crt = Math.max(root.val, Math.max(root.val + left, root.val + right));
max[0] = Math.max(max[0], Math.max(crt, root.val + left + right));
return crt;
}
}
|