O(1) space O(n) time Simple Java solution with detail explanation


  • 0
    Z
    /**
     * Use int[2] to maintain two possible conditions
     * 
     * 1.         a
     *         b     c 
     * 
     * 2.    a   or   a
     *     b              c
     * 
     * 3. **We have to deal with the condition where negative number occurs**
     *  Negative number may exist in both of these two conditions
     *
     * If either of b & c or both b & c is negative, condition 1 & 2 becomes same.(Add negative number is    
     * the last choice for this problem **if the tree only contains negative number**
     * 
     * If both b & c is positive, we calculate condition 1 and 2 separately. Pay attention that max[0] 
     * maintains the maximum value among all possible condition 1. **Rather than the current node.**
     *
     * The reason why we maintain two separate conditions is that 
     * if condition 1 gets the current maximum value, this maximum value
     * can't be used for further calculation since we get a TWISTED path here,
     * any parent node access to node a can only go one direction rather go either way.
     */
    public int maxPathSum(TreeNode root) {
        
        int[] max = traverse(root);
        
        return Math.max(max[0],max[1]);
    }
    
    public int[] traverse(TreeNode root){
        
        int[] result = {Integer.MIN_VALUE,Integer.MIN_VALUE};
        
        if(root==null) return result;
        
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);
        
        int curMax = 0;
        int pathMax = 0;
        if(left[1]<0 && right[1]<0){
            curMax = root.val;
            pathMax = root.val;
        }else if(left[1]<0 || right[1]<0){
            curMax = root.val+((left[1]<0)?right[1]:left[1]);
            pathMax = curMax;
        }else{
            curMax = root.val+left[1]+right[1];
            pathMax = root.val+Math.max(left[1],right[1]);
        }
        
        result[0] = Math.max(Math.max(curMax,left[0]),right[0]);
        result[1] = pathMax;
        
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.