124. Binary Tree Maximum Path Sum

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Analysis:

 At each node, the potential maximum path could be one of these cases:

 i. max(left subtree) + node 

ii. max(right subtree) + node 

iii. max(left subtree) + max(right subtree) + node 

iv. the node itself 

If max(left) or max(right) is less than 0, no need to count them. So treat them as 0. The max function is not the result, is the max sum from root top down. The current max left + right + root.val, is the max value of the path that root as highest point (lowest common ancestor). 

Solution:

 /**  
  * Definition for a binary tree node.  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 class Solution {  
   int max = Integer.MIN_VALUE;  
   public int maxPathSum(TreeNode root) {  
     maxDown(root);  
     return max;  
   }  
   private int maxDown(TreeNode root) {  
     if (root == null) return 0;  
     int left = maxDown(root.left);  
     int right = maxDown(root.right);  
     max = Math.max(max, left + right + root.val);  
     int res = Math.max(left + root.val, right + root.val);  
     return res < 0 ? 0 : res;  
   }  
 }