3.2 Max Path Sum II

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from 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

Input: TreeNode root

Output: int max path sum from any node to any node

Solution:

1. Same as 3.1. The return value to the parent is not the same as what to get at current layer.

2. Since the path always exists (start and end can be the same), if root == null, return 0 is fine.

3. Need to consider when either the sum of left or sum of right is negative.

public int maxPathSumII(TreeNode root) {
  int[] max = new int[] {Integer.MIN_VALUE};
  helper(root, max);
  return max[0];
}

private int helper(TreeNode root, int[] max) {
  if (root == null) { return 0; }
  int left = helper(root.left, max);
  int right = helper(root.right, max);
  
  left = left < 0 ? 0 : left;
  right = right < 0 ? 0 : right;

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