Given a binary tree in which each node contains an integer number. Find the maximum possible subpath sum(both the starting and ending node of the subpath should be on the same path from root to one of the leaf nodes, and the subpath is allowed to contain only one node).

Assumptions

• The root of given binary tree is not null

Examples

-5

/ \

2 11

 /    \

6     14

       /

    -3

The maximum path sum is 11 + 14 = 25

Solution: 直链中和最大路径。可以从上到下传值，或者从下到上返值，遇到负数和的取0。每个node都要更新max

Top down:

  int max = Integer.MIN_VALUE;
  public int maxPathSum(TreeNode root) {
    if (root == null) {
      return 0;
    }
    helper(root, 0);
    return max;
  }
  private void helper(TreeNode root, int preSum) {
    int sum = preSum + root.key;
    max = Math.max(max, sum);
    sum = Math.max(sum, 0);
    if (root.left != null) {
      helper(root.left, sum);
    }
    if (root.right != null) {
      helper(root.right, sum);
    }
  }

Bottom up:

  int max = Integer.MIN_VALUE;
  public int maxPathSum(TreeNode root) {
    if (root == null) {
      return 0;
    }
    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 = Math.max(left, right) + root.key;
    max = Math.max(max, sum);
    return sum;
  }