Python BFS (None-Pythonic)


  • 0
    W

    For non-iterative DFS, please go here. The following is the BFS solution using list to mimic queue. Code is not Pythonic (I am not a Python experts) but readable to myself.

    class Solution(object):
        def isSameTree(self, p, q):
            """
            :type p: TreeNode
            :type q: TreeNode
            :rtype: bool
            """
            # bfs
            queue = [(p,q)]
            while queue:
                size = len(queue)
                for i in xrange(size):
                    # pop from front for length-of-queue times
                    p1,q1 = queue.pop(0)
                    # each time: none for both nodes then continue
                    if not p1 and not q1: continue
                    
                    # if only one of two nodes is None, apparently False
                    if (p1 or q1) and not (p1 and q1): return False
                    
                    # Not identical values: False
                    if p1.val!=q1.val: return False
                    
                    # push back subtrees
                    queue.append((p1.left,q1.left))
                    queue.append((p1.right,q1.right))
            return True
    

Log in to reply
 

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