My Python iterative DFS solution


  • 6
    C
    def hasPathSum(self, root, sum):
        if root is None:
            return False
        stack = [(root, sum)]
        while stack:
            node, _sum = stack.pop()
            if node.left is node.right is None and node.val == _sum:
                return True
            if node.left:
                stack.append((node.left, _sum - node.val))
            if node.right:
                stack.append((node.right, _sum - node.val))
        return False
    

    Current node and the sum until current node as a tuple is pushed onto the stack to keep track of the sum.


  • 0
    Q

    Thank you for your sharing!


  • 0
    Y

    Could you please explain "if node.left is node.right is None"?


  • 0
    C

    It is the same as if node.left is None and node.right is None, I probably shouldn't code that way, it's shorter but less idiomatic.


  • 0
    Y

    That makes lots of sense! Thanks so much.


  • 0

    The most simple iterative solution I have seen. Thanks for your sharing.


Log in to reply
 

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