My java solution


  • 0
    T

    basic idea is the few lines of comment in the beginning of maxPathSum2(). this method returns 2 numbers, the best COMPLETE path under this current root, not necessarily including root; and the best path ending at root, called "partial" . the formulation of the problem does not allow null to be considered a path of cost 0, so I had to do a lot of tweaks which made the flow look less nice

    /**
     * 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) {
            return maxPathSum2(root)[0];
        }
        
        int[]  maxPathSum2(TreeNode root) {
            // (fullLeft, halfLeft ) = maxPathSum(root.left);
            // (fullRight, halfRight) = maxPathSum(root.right);
            
            // return { max(fullLeft , fullRight, halfLeft + root.val + halfRight ),
            //   max(halfLeft, halfRight) + root.val
            // };    
            if (root == null) return new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
            
            
            int left[] = maxPathSum2(root.left);
            int right[] = maxPathSum2(root.right);
            
            // if the sub trees produce negative , just ignore
            // left[0] = Math.max(0, left[0]);
            // left[1] = Math.max(0, left[1]);
            // right[0] = Math.max(0, right[0]);     
            // right[1] = Math.max(0, right[1]); 
            
            int full = root.val;
            if (root.left != null && left[1] >0 )
                full+= left[1];
            
            if (root.right !=null && right[1] > 0 )
                full += right[1];
                
            int partial = root.val;
            if (root.left !=null) {
                full = Math.max(full, left[0]);
                partial = Math.max(partial, root.val + left[1]);
            }
                
            if (root.right !=null) {
                full = Math.max(full, right[0]);
                        partial = Math.max(partial, root.val + right[1]);
            }
    
            return new int[]{
                full, 
                partial
            };
        }
    }

Log in to reply
 

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