Python BFS easy understanding


  • 1
    W
    class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        ## BFS
        if not root:
            return False
        queue = collections.deque([(root,root.val)])
        while queue:
            node, val = queue.popleft()
            if not node.left and not node.right and val == sum:
                return True
            if node.left:
                queue.append((node.left, val+node.left.val))
            if node.right:
                queue.append((node.right, val+ node.right.val))
        return False

Log in to reply
 

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