One shot two kills - Same Tree | Symmetric Tree


  • 0
    D
    1. Same Tree
    2. Symmetric Tree
      The way approaching these two problems are very similar. Only difference is that Symmetric Tree compares left node to right node.

    Recursive Solution 110. Same Tree 101. Symmetric Tree

    class Solution:
       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
    
    class Solution(object):
        def isSymmetric(self, root):
            if not root: return True
            def check(p, q):
                if p and q:
                    return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)
                return p == q
            return check(root.left, root.right)
    

    As you can see, isSymmetric compare left to right and right to left.


    Here is iteration solution.

    class Solution(object):
        def isSameTree(self, p, q):
            stack = [(q, p)]
            while stack:
                n1, n2 = stack.pop()
                if n1 and n2 and n1.val != n2.val:
                    return False
                elif n1 and n2:
                    stack += [(n1.right, n2.right), (n1.left, n2.left)]
                elif n1 or n2:
                    return False
            return True
    
    class Solution(object):
        def isSymmetric(self, root):
            if not root: return True
            stk = [(root.left, root.right)]
            while stk:
                n1, n2 = stk.pop()
                if n1 and n2 and n1.val != n2.val:
                    return False
                elif n1 and n2:
                    stk += (n1.left, n2.right), (n1.right, n2.left),
                elif n1 or n2:
                    return False
            return True
    

Log in to reply
 

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