Iterative DFS solution with two stacks


  • 0
    H
    1. push root and all its left children,
    2. pop. If it has right child, repeat 1.

    class Solution:

    def isSameTree(self, p, q):
        if not p and not q: return True
        elif not p or not q: return False
    
        stack1 ,stack2= [],[]
    
        if not self.f(p,q,stack1,stack2):
            return False
    
        while stack1 and stack2:
            tmp1=stack1.pop(0)
            tmp2=stack2.pop(0)
    
            if tmp1.right:
                if tmp2.right:
                   if not self.f(tmp1.right,tmp2.right,stack1,stack2):
                       return False
                else:
                    return False
            elif tmp2.right:
                return False
        return True
    
    def f(self,p,q,stack1,stack2):
        while p:
            stack1.append(p)
            if not q:
                return False
            stack2.append(q)
            if p.val!=q.val:
                return False
            q=q.left
            p=p.left
        if q:
            return False
        return True

Log in to reply
 

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