(leetcode 문제 풀이) Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Constraints:
1. The number of nodes in the tree is in the range [1, 1000].
2. -100 <= Node.val <= 100

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        left_visited = []
        right_visited = []
        
        q = deque()
        
        # left subtree
        if root.left:
            q.append((root.left, root.left.val))
        while q:
            n, v = q.popleft()
            left_visited.append(v)
            
            if v == None:
                continue
            
            if n.left:
                q.append((n.left, n.left.val))
            else:
                q.append((n.left, None))
            
            if n.right:
                q.append((n.right, n.right.val))
            else:
                q.append((n.right, None))
        
        if root.right:
            q.append((root.right, root.right.val))
        while q:
            n, v = q.popleft()
            right_visited.append(v)
            
            if v == None:
                continue
            
            if n.right:
                q.append((n.right, n.right.val))
            else:
                q.append((n.right, None))
            
            if n.left:
                q.append((n.left, n.left.val))
            else:
                q.append((n.left, None))
                
        if left_visited == right_visited:
            return True
        else:
            return False

이번 문제는 BST를 활용하여 해결했던 문제다. 루트노드를 중심으로 왼쪽과 오른쪽이 mirroring하고 있는지 살펴보면 되기 때문에 왼쪽 subtree와 오른쪽 subtree를 따로 살펴보았다.

주의할 점은 왼쪽 subtree와 오른쪽 subtree가 똑같은 것이 아니라 거울처럼 반대로 비춰져야 한다는 것이다. 따라서 왼쪽 subtree를 순회할 때는 왼쪽 -> 오른쪽 방향으로 진행해야 하고, 오른쪽 subtree를 순회할 때는 오른쪽 -> 왼쪽 방향으로 진행해야 한다.

최종적으로 left_visited에 담긴 원소들과 right_visited에 담긴 원소들이 동일하면 True를, 다르다면 False를 리턴하면 된다.

---

위 코드처럼 로직을 차례대로 따라가며 구현해도 되지만 또 다른 로직이 있다. 왼쪽 subtree 따로, 오른쪽 subtree 따로 진행하지 않고 동시에 살펴보는 것이다. 한 level씩 내려가면서 자식 노드가 있다면 1) 왼쪽 subtree의 왼쪽 자식노드와 오른쪽 subtree의 오른쪽 자식노드가 같은지, 2) 왼쪽 subtree의 오른쪽 자식노드와 오른쪽 subtree의 왼쪽 자식노드가 같은지 확인하면 된다.

아래는 이 로직을 재귀구조로 구현한 코드이다. 확실히 위의 코드보다 훨씬 간결해진 느낌이다.

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def traversal(left, right):
            if not left and not right:
                return True
            elif not left or not right:
                return False
            else:
                return left.val == right.val and traversal(left.left, right.right) and traversal(left.right, right.left)
            
        return traversal(root, root)