【Python】Recursive solution with explanation and thinking process

  • 5

    Base case

    1. This question wants to find a path from node to the leaf, so the node who satisfies must be a leaf (not node.left and not nood.right)
    2. I want to recursively subtract the sum by current node's value, so the leaf node of correct path must have the same value of its assigned sum

    Recursive step

    1. We want to traverse all the nodes, so node.left and node.right must be called parallelly
    2. One valid path is enough, so we want to use or to connect two "branches"
    3. Considering each node as the root of its children, sum should be modified from its parent

    def hasPathSum(self, root, sum):
        if not root:
            return False
        if root.val == sum and not root.left and not root.right:
            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.