Backtracking & Dynamic Programming Solution - Binary Tree Maximum Path Sum ***

The idea is to have an array which contains two elements: One element to save max paths between left & right child; Second is used to save other paths which may not contain current node at all or cross left and right of current node or element ONE. By doing this…. the code guarantees to have all max cases saved…

The hard part is to realize and come up with a way to save previous max (not contain current node at all)!!! The array can be replaced with two variables…one for max(element TWO) and the other for temp (element ONE)...

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root){
        if(root == null){
            return 0;
        }
        int[] result = maxSumPathFinder(root);
        return result[1];
    }
 
    private int[] maxSumPathFinder(TreeNode root){
        int[] results = new int[2];
        if(root == null){
            results[0] = Integer.MIN_VALUE;
            results[1] = Integer.MIN_VALUE;
            return results;
        }
        int[] leftMax = maxSumPathFinder(root.left);
        int[] rightMax = maxSumPathFinder(root.right);
     
        results[0] = Math.max((leftMax[0]>0? leftMax[0]:0) + root.val, (rightMax[0] > 0? rightMax[0]:0) + root.val);
        results[1] = Math.max(leftMax[1], Math.max(rightMax[1], Math.max((leftMax[0]>0? leftMax[0]:0) + root.val + (rightMax[0] > 0? rightMax[0]:0), results[0])));
        return results;
    }
}