Write a program to find maximum path sum in a binary tree. The path need not to be passed from root.

     6
   /  \
  3    10
 / \   / \
1   4 7   8

Maximum path sum
25 - [7,10,8]

The trick to solve the problem is to do bottom up approach.

A recursive method maxPathDown(TreeNode node)

(1) computes the maximum path sum with highest node is the input node, update maximum if necessary.

(2) returns the maximum sum of the path that can be extended to input node's parent.

public class MaxPathSum {
	int maxValue = 0;
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }

    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}