Maximum Path Sum Binary Tree I

Medium

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 Integer.MIN_VALUE(Java)/INT_MIN (C++).

Examples

-15

/ \

2 11

/ \

6 14

The maximum path sum is 6 + 11 + 14 = 31.

Solution:

To Parent: return root.key + max(left path, right path)

At Current: update globalMax against root.key + left path + right path

From Children: largest sum left path and largest sum right path

public class Solution {
  public int maxPathSum(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;
    }

    if (root.right == null && root.left == null) {
      return root.key;
    } else if (root.right == null) {
      return helper(root.left, max) + root.key;
    } else if (root.left == null) {
      return helper(root.right, max) + root.key;
    } else {
      //case 4
      // from children
      // get best partial paths from left and right
      int bestLPath = helper(root.left, max);
      int bestRPath = helper(root.right, max);

      // at current
      // compare completeLocalPath to global maximum path
      int completeLocalPath = bestLPath + root.key + bestRPath;
      max[0] = Math.max(max[0], completeLocalPath);

      // to parent
      // pass up best partial path
      return Math.max(bestLPath, bestRPath) + root.key;
    }
  }
}

Mistakes Made:

problem constraint states a valid path must be from one leaf node to another. This means that we can only update the global maximum if we have both a left and right child