3.3 Max Path Sum III

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 the given binary tree is not null

Solution 1: DFS top-down: carry a path-prefixSum while traversing the tree from root to leaf node

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

private void helper(TreeNode root, int[] max, int prefixSum) {
  int globalSum = prefixSum + root.key;
  max[0] = Math.max(globalSum, max[0]);
  globalSum = Math.max(globalSum, 0);
  if (root.left != null) {
    helper(root.left, max, globalSum);
  }
  if (root.right != null) {
    helper(root.right, max, globalSum);
  }
}

Solution 2: Bottom-up

1. What to expect from left/right subtree?

max path sum from root to leaf on the left/right subtree

2.What to do at the current layer?

Math(leftMax, rightMax) + root.key

3. What to report to the parent?

return globalSum of the path from root to leaf

public int maxPathSumIII(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 = Math.max(helper(root.left, max), 0);
  int right = Math.max(helper(root.right, max), 0);
  int globalSum = Math.max(left, right) + root.key;
  max[0] = Math.max(globalSum, max[0]);
  return globalSum;
}