Leetcode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Understand the problem:
As described in the problem, the problem asks for finding the maximum path sum of a binary tree. The tricky part is the path may start and end at any node in the tree. Note that the path should never contain repeated nodes, i.e, the path should not contain a node more than once.  For example, for a binary tree,
             1
            /   \
         -3     5
         /  \    /
        5  1 10
The maximal path sum is 5 -> -3 -> 1 -> 5 -> 10, which equals to 18.

Solution:
We can solve the problem using post-order traversal recursively. The key is the return value. What gonna be returned in the post-order traversal? The return value should be the maximum of the three cases:

• parent node value
• parent + left child
• parent + right child

In addition, we should also consider the case that max value could be also parent + left + right. It is a possible path, but this path should never be returned back since each node can be only visited once. So the maximum path sum is the maximum value of the above three cases and the parent+left+right. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = Integer.MIN_VALUE; 
 public int maxPathSum(TreeNode root) {
     
     findMax(root);
     
     return max;
 }
 
 private int findMax(TreeNode root) {
     if (root == null) return 0;
     
     int left = findMax(root.left);
     int right = findMax(root.right);
     
     int arch = left + root.val + right;
     int maxPathSum = Math.max(root.val, Math.max(left, right) + root.val);
     
     max = Math.max(max, Math.max(arch, maxPathSum));
     
     return maxPathSum;
 }
}

Summary:
It is not an easy problem. But if you could think of the post-order traversal, and the four cases of the max value, as well as the return value of the post-order traversal, the problem is not very hard. Do understand every detail of the code.


Update 9/30/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        maxPathSumHelper(root);
        return maxSum;
    }
    
    private int maxPathSumHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = maxPathSumHelper(root.left);
        int right = maxPathSumHelper(root.right);
        
        int arch = left + right + root.val;
        
        int pathSum = Math.max(root.val, Math.max(left, right) + root.val);
        
        maxSum = Math.max(maxSum, Math.max(arch, pathSum));
        
        return pathSum;
    }
}