Binary Tree Maximum Path Sum

Given a 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 does not need to go through the root.

For example: Given the below binary tree,

   1
  / \
 2   3

Return 6.

Solution I:

Note: need to maintain a global max and local max because the max sum does not necessarily happen from root to leaf

Try the bottom up approach. At each node, the potential maximum path could be one of these cases:

• i. max(left subtree) + node
• ii. max(right subtree) + node
• iii. max(left subtree) + max(right subtree) + node
• iv. the node itself

Then, we need to return the maximum path sum that goes through this node and to either one of its left or right subtree to its parent. There’s a little trick here: If this maximum happens to be negative, we should return 0, which means: “Do not include this subtree as part of the maximum path of the parent node”, which greatly simplifies our code.

public class Solution {
    private int maxSum;
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        findMax(root);
        return maxSum;
    }

    private int findMax(TreeNode p) {
        if (p == null) return 0;
        int left = findMax(p.left);
        int right = findMax(p.right);
        maxSum = Math.max(p.val + left + right, maxSum);
        int ret = p.val + Math.max(left, right);
        return ret > 0 ? ret : 0;
    }
}

Solution II:

public class Solution {
    public int maxPathSum(TreeNode root) {
    int max[] = new int[1]; 
    max[0] = Integer.MIN_VALUE;
    calculateSum(root, max);
    return max[0];
}

public int calculateSum(TreeNode root, int[] max) {
    if (root == null)
        return 0;

    int left = calculateSum(root.left, max);
    int right = calculateSum(root.right, max);

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

    max[0] = Math.max(max[0], Math.max(current, left + root.val + right));

    return current;
}
}