Python Recursive, DFS + stack, BFS + queue


  • 0
    # DFS + stack
    class Solution(object):
        def isSameTree(self, p, q):
            stack = [(q, p)]
            while stack:
                n1, n2 = stack.pop()
                
                if n1 and n2:
                    if n1.val != n2.val:
                        return False
                    stack += [(n1.right, n2.right), (n1.left, n2.left)]
                elif n1 or n2:
                    return False
                else:
                    continue
                
            return True
    
    # BFS + queue
    class SolutionBFS(object):
        def isSameTree(self, p, q):
            queue = [(p, q)]
            while queue:
                n1, n2 = queue.pop(0)
                
                if n1 and n2:
                    if n1.val != n2.val:
                        return False
                    # put 2 lefts, 2 rights, order doesn't matter
                    queue += [(n1.left, n2.left), (n1.right, n2.right)]
                elif n1 or n2:
                    return False
                else:
                    continue
                
            return True
            
    
    # Recursive
    class SolutionRecursive(object):
        def isSameTree(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)
            return p == q
    

Log in to reply
 

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