[LeetCode] Symmetric Tree 파이썬 (iterative, recursion)

iterative solution (32ms)

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        if root is None:
            return True
        stack = []
        stack.append(root.left)
        stack.append(root.right)

        while stack:
            p, q = stack.pop(), stack.pop()

            if p is None and q is None:
                continue

            if p is None or q is None or p.val != q.val:
                return False

            stack.append(p.left)
            stack.append(q.right)

            stack.append(p.right)
            stack.append(q.left)

        return True

stack으로 만들어서 초기 left, right값을 넣어주고

p, q (즉 left, right node)가  없다면 (맨 꼭대기 노드라면) 아래 코드 실행하지 않고 다시 while문으로 오게 되는데

이때는 stack에 아무것도 없기 때문에 바로 while 문 종료하면서 return True

 

꼭지점 체크 문 다음에 있는 if 문을 살펴보면 ( if p is None or q is None or p.val != q.val: )

p(left) 노드가 없거나, q 노드가 없거나 left와 right이 다르다면 symmetric 조건에 어긋나기 때문에 return False

 

위 두 조건에 해당이 안되는 경우

( 꼭지점이 아니고, symmetric인 상황이라면 2 level tree 인 경우)

stack에 넣어주는데

symmetric 조건에 맞춰야 하기 때문에 left right right left 순으로 넣어 준다.

 

 

---

 

 

recursion solution

class Solution2:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        if root is None:
            return True

        return self.isSymmetricRecu(root.left, root.right)

    def isSymmetricRecu(self, left, right):
        if left is None and right is None:
            return True
        if left is None or right is None or left.val != right.val:
            return False
        return self.isSymmetricRecu(left.left, right.right) and self.isSymmetricRecu(left.right, right.left)

isSymmetricRecu 함수를 보면,

첫 번째 if 문에서 꼭지점인지 여부 체크

두번째 if 문에서 symmetric 여부 체크

마지막 return에서 left, right, right, left 순으로 recursion

 

---

28ms 솔루션

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        
        def helper(lsub, rsub):
            
            if not lsub and not rsub: return True
            if not lsub or not rsub: return False
            
            r = helper(lsub.right, rsub.left)
            l = helper(lsub.left, rsub.right)
          
            return (lsub.val == rsub.val) and r and l
        
        
        

        return helper(root.left, root.right)