Python solution with DFS

  • 0

    The solution recursively take current node's child until it reach the bottom (leave node), if there is a value of one path reaches the sum, return true.

    def hasPathSum(self, root, sum):
        if root == None:
            return False
        return self.DFS(root, 0, sum)
    def DFS(self, root, value, sum):
        if root.left == None and root.right==None:
            if root.val+ value == sum:
                return True
        if root.left != None and root.right != None:
            return self.DFS(root.left, value+root.val, sum) or self.DFS(root.right, value+root.val, sum)
        elif root.left != None:
            return  self.DFS(root.left, value+root.val, sum)
        elif root.right != None:
            return self.DFS(root.right, value+root.val, sum)
        return False

Log in to reply

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