Python DFS o(n) beat 80%


  • 1
    Y

    this is the solution;
    '''
    class Solution(object):
    def maxPathSum(self, root):
    self.m=root.val
    self.helper(root)
    return self.m

    def helper(self,node):
        if not node:
            return None
        l=self.helper(node.left)
        l=(l if l and l>0 else 0)
        r=self.helper(node.right)
        r=(r if r and r>0 else 0)
        res=max(l,r)+node.val
        self.m=max(self.m,l+r+node.val)
        return res
    

    '''


Log in to reply
 

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