Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.

Couple scenarios to consider -

• Node only (there may be negative value in node)
• L-sub + Node
• R-sub + Node
• L-sub + Node + R-sub - arch

We need to compare each situation to find the max

The recursive method need to return the max between node, node+L-sub, node+R-sub and exclude arch because from the arch you can not go through the root's parent again.

    1
   / \
  2   3
 / \   \
4  5    6

when we calculate the leftMax and rightMax for node(1), the left max should not return 4->2->5 (arch), because this is not a valid path which will go through node(1).

public int maxPathSum(TreeNode root) {
        int[] maxNode = new int[1];
        maxNode[0] = Integer.MIN_VALUE;
        findMax(root, maxNode);        
        return maxNode[0];
    }

    /*

     */
    public int findMax(TreeNode root, int[] maxNode) {
        if (root==null) {
            return 0;
        }

        int left = findMax(root.left, maxNode);
        int right = findMax(root.right, maxNode);
        int arch = root.val+left+right;

        int maxPathAcrossRootToParent = Math.max(root.val, Math.max(left, right)+root.val);
        maxNode[0] = Math.max(maxNode[0], Math.max(maxPathAcrossRootToParent, arch));

        return maxPathAcrossRootToParent;        
    }