Python - 80ms - Recursive DFS Pre-Order solution - O(n)

  • 1
    class Solution:
        # @param {TreeNode} root
        # @param {integer} sum
        # @return {boolean}
        def hasPathSum(self, root, sum):
            if root is None: return False
            cur_sum = sum - root.val
            if cur_sum == 0 and is_leaf(root): return True
            return self.hasPathSum(root.left, cur_sum) or \
                    self.hasPathSum(root.right, cur_sum)
    def is_leaf(root):
        return not root.left and not root.right

  • 2

    Good answer, while it seems can be rewritten as:

    def hasPathSum(self, root, sum):
        if not root:
            return False
        if not root.left and not root.right:
            if sum == root.val:
                return True
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

Log in to reply

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