Given a binary tree in which each node contains an integer number. Find the maximum possible sumfrom one leaf node to another leaf node.If there is no such path available, return Integer.MIN_VALUE(Java)/INT_MIN (C++).

Examples

-15

/ \

2 11

 /    \

6     14

The maximum path sum is 6 + 11 + 14 = 31.

Solution: 注意是leaf to leaf，所以只有root.left != null && root.right != null时才更新max。注意recursion返回的是一支路径

  int max = Integer.MIN_VALUE;
  public int maxPathSum(TreeNode root) {
    if (root == null || root.left == null || root.right == null) {
      return max;
    }
    helper(root);
    return max;
  }
  private int helper(TreeNode root) {
    if (root == null) {
      return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);

    //left和right非空时才更新max
    if (root.left != null && root.right != null) {
      int sum = root.key + left + right;
      max = Math.max(max, sum);
      return Math.max(left, right) + root.key;
    }
    //注意不是return Math.max(left, right) + root.key; eg:  
      1
     / \
       -1  应该返回非空的那支路径
    return root.left == null ? right + root.key : left + root.key;
  }