Python Recursive solution and DFS Iterative solution with stack and BFS Iterative solution with queue


  • 12
    C
    def isSameTree1(self, p, q):
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return p == q
    
    # DFS with stack        
    def isSameTree2(self, p, q):
        stack = [(p, q)]
        while stack:
            node1, node2 = stack.pop()
            if not node1 and not node2:
                continue
            elif None in [node1, node2]:
                return False
            else:
                if node1.val != node2.val:
                    return False
                stack.append((node1.right, node2.right))
                stack.append((node1.left, node2.left))
        return True
     
    # BFS with queue    
    def isSameTree3(self, p, q):
        queue = [(p, q)]
        while queue:
            node1, node2 = queue.pop(0)
            if not node1 and not node2:
                continue
            elif None in [node1, node2]:
                return False
            else:
                if node1.val != node2.val:
                    return False
                queue.append((node1.left, node2.left))
                queue.append((node1.right, node2.right))
        return True

  • 5
    C

    A revised version of the DFS with stack case which is easier to understand:

    # dfs + stack
    def isSameTree(self, p, q):
        stack = [(p, q)]
        while stack:
            n1, n2 = stack.pop()
            if n1 and n2 and n1.val == n2.val:
                stack.append((n1.right, n2.right))
                stack.append((n1.left, n2.left))
            elif not n1 and not n2:
                continue
            else:
                return False
        return True

  • 0
    C

    excuse me can u tell me what's the meaning of : if p and q: thank you


  • 0
    M

    it means: if (p is not None) and (q is not None)


Log in to reply
 

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