Python BFS code


  • -1
    Z

    class Solution(object):

    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        
        queue = []
        queue.append(root)
        result_list = []
        result_list.append((root, 0)) # node, root_to_node_sum
        while queue:
            next_level_result = []
            next_level_queue = []
            for idx, element in enumerate(queue):
                node, parent_val = result_list[idx]
                if node.val + parent_val == sum and node.left is None and node.right is None:
                    return True
                sum_root_to_element = node.val + parent_val
                if element.left:
                    next_level_queue.append(element.left)
                    next_level_result.append((element.left, sum_root_to_element))
                if element.right:
                    next_level_queue.append(element.right)
                    next_level_result.append((element.right, sum_root_to_element))
            queue = next_level_queue
            result_list = next_level_result
        return False

Log in to reply
 

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