Given a binary tree in which each node element contains a number. find the maximum possible sum from one leaf node to another. (any leaf node to another leaf node)

key point : only need to update the global max when the root have both left and right child, in this case meet the condition of leaf node to leaf node path.

the value that return to the upper level is

max(left,right) + root.key when both left,right child are not null

left+ root.key if left != null, right + root.key if right != null

solution 1 : O(n)

/**

* 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;
    }
}