Given a binary tree in which each node contains an integer number. Find the maximum possible sumfrom any node to any node (the start node and the end node can be the same).

Assumptions

• ​The root of the given binary tree is not null

Examples

-1

/ \

2 11

 /    \

6    -14

one example of paths could be -14 -> 11 -> -1 -> 2

another example could be the node 11 itself

The maximum path sum in the above binary tree is 6 + 11 + (-1) + 2 = 18

Solution: 子树sum小于0时不取。因为是any to any node，所以每个node也更新max。recursion返回的是一支路径

  int max = Integer.MIN_VALUE;
  public int maxPathSum(TreeNode root) {
    helper(root);
    return max;
  }
  private int helper(TreeNode root) {
    if (root == null) {
      return 0;
    }
    //取非负的
    int left = Math.max(helper(root.left), 0);
    int right = Math.max(helper(root.right), 0);
    int sum = root.key + left + right;
    max = Math.max(max, sum);
    return Math.max(left, right) + root.key;
  }

或者用ResultType把root2any和any2any结果封装：

    private class ResultType{
        int root2any, any2any;

        public ResultType(int root2any, int any2any){
            this.root2any = root2any;
            this.any2any =any2any;
        }
    }

    public int maxPathSum(TreeNode root) {
        return helper(root).any2any;
    }    

    private ResultType helper(TreeNode root){    
        if(root == null){
            return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        int root2any = Math.max(Math.max(left.root2any, right.root2any), 0) + root.val;
        int any2any = Math.max(left.any2any, right.any2any);
        any2any = Math.max(any2any, Math.max(left.root2any, 0) + Math.max(right.root2any, 0) + root.val);

        return new ResultType(root2any, any2any);
    }