[LeetCode] Problem 124 - Binary Tree Maximum Path Sum

Posted on | In ,

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example

No.1

Input: [1,2,3]

1
2
3
  1
 / \
2   3

Output: 6

No.2

Input: [-10,9,20,null,null,15,7]

1
2
3
4
5
 -10
 / \
9  20
  /  \
 15   7

Output: 42

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxPathSumHelper(root);
    return max;
}

private int maxPathSumHelper(TreeNode root) {
    if (root == null)
        return 0;

    int left = Math.max(maxPathSumHelper(root.left), 0);
    int right = Math.max(maxPathSumHelper(root.right), 0);
    max = Math.max(max, root.val + left + right);

    return Math.max(left, right) + root.val;
}