Get maximum sum of path cost from any node to any node(not necessary from leaf to leaf)

key point:

discard the left subtree path if left subtree path sum < 0

discard the right subtree path if right subtree path sum < 0

globalmax = max(globalMax, root.key + left + right)

the value that need to return to the upper level is root.key + max(left,right) ( must include root, need to include at least one node in this path, otherwise it happens not including any node in the path)

/**

* public class TreeNode {

* public int key;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int key) {

* this.key = key;

* }

* }

*/

public class Solution {
    public int maxPathSum(TreeNode root) {
        // Write your solution here.

        int[] globalMax = {Integer.MIN_VALUE};

        pathSum(root,globalMax\);

        return globalMax[0];
    }

    public int pathSum (TreeNode root,int[] globalMax) {
        if (root == null) {

          return 0;

        }

        // base case

        int left = pathSum(root.left,globalMax);

        int right = pathSum(root.right,globalMax);



        if (root.left != null && root.right != null) {

            globalMax[0] = Math.max(globalMax[0],left + right + root.key\);

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

        }

        return root.left == null ? right + root.key : left + root.key;
    }
}