My Accepted python solution


  • 0
    L

    this solution uses recursive, for a node return (value,left+value,right+value,left+value+right);

    and uses this info to compare.

    class Solution:
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        # @return (root.val,left+root.val,right+root.val,left+right+root);
        def getNodeMaxValue(root):
            if(root.left==None and root.right==None):
                return (root.val,root.val,root.val,root.val);
            
            # should set to the min int number.
            l1,l2,l3,l4,r1,r2,r3,r4=-100,-100,-100,-100,-100,-100,-100,-100;
    
            if(root.left !=None):
                l1,l2,l3,l4=getNodeMaxValue(root.left);
            if(root.right!=None):
                r1,r2,r3,r4=getNodeMaxValue(root.right);
            
            #print((root.val,   
            #       max(l1,l2,l3)+root.val,
            #       max(r1,r2,r3)+root.val,
            #       max(l1,l2,l3,l4,r1,r2,r3,r4,max(l1,l2,l3)+root.val+max(r1,r2,r3))));
            return (root.val,   
                   max(l1,l2,l3)+root.val,
                   max(r1,r2,r3)+root.val,
                   max(l1,l2,l3,l4,r1,r2,r3,r4,max(l1,l2,l3)+root.val+max(r1,r2,r3)));
    
        return max(getNodeMaxValue(root));

Log in to reply
 

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