3.1 Max Path Sum I

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return.

Input: TreeNode root

Output: int max path sum from leaf node to another leaf node

Corner case: if root == null, what to return if no such path (only one leaf node)? Return a special value Integer.MIN_VALUE. Cannot just return -1 because it could be the sum.

Solution:

1. Solved with DFS. What to expect from left/right child?

left: max "root to leaf" path sum of left sub

right: max "root to leaf" path sum of right sub

2. What to do at the current layer?

Calculate left + right + root.key

update globalMax if needed

3. What to report to the parent?

max path sum from root to leaf

return max(left, right) + root.key

cannot update globalMax if one child == null, return 0

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