Simple Python DFS


  • 0
    C
    class Solution(object):
        def __init__(self):
            self.maxsum = -sys.maxint
            
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            def dfs(node):
                if not node.left and not node.right:
                    self.maxsum = max(self.maxsum, node.val)
                    return node.val
                l = 0
                r = 0
                if node.left:
                    l = dfs(node.left)
                if node.right:
                    r = dfs(node.right)
                self.maxsum = max(self.maxsum, node.val, node.val+l, node.val+r, node.val+l+r)
                return max(node.val, node.val+l, node.val+r)
            
            dfs(root)
            return self.maxsum
    

Log in to reply
 

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