[Leetcode/파이썬] 101. Symmetric Tree

Symmetric Tree

---

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

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

 

Constraints:

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

 

Follow up: Could you solve it both recursively and iteratively?

 

# 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
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def check(p, q) :
            if not p and not q :
                return True

            if not p or not q or p.val != q.val :
                return False

            return check(p.left, q.right) and check(p.right, q.left)

        return check(root.left, root.right)
'''
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        stack = [root.left, root.right]

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

            if not p and not q :
                continue
            if not p or not q 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

'''

문제 제목에서도 알 수 있듯이 데칼코마니인지 아닌지 찾는 문제이다. 두 가지 방법으로 해결하였다. 추천 방법에 재귀와 반복을 사용해서 풀어볼래? 라고 적혀있어서 힌트를 굳이 보지 않아도 재귀나 스택을 활용하는 방법이라는 것을 알 수 있었다. 조금 더 확장하자면 완전탐색 중 그래프와 연관이 깊은 BFS나 DFS까지도 생각해볼 수 있지 않을까 라고 생각이 든다. 

문제를 살펴보자. 이거 아마 언젠간 푼 적 있는 문제의 연장선이라고 생각이 들었다. 100번 Same Tree 문제와 매우 유사하다는 것을 알 수 있었다. 늘 그렇듯 오랜만에 보니까 늘 새롭다. 

문제 조건에 노드 번호가 1~1000 번 까지 있기 때문에 1번은 무조건 존재한다. 그리고 그 다음, 2번을 찾으러 가는데 root.left.val 과 root.right.val 이 같은지 다른지 판별해야한다. 다르다면 바로 False, 같으면 어디까지 같은지 계속해서 내려간다. 찾으러 내려갈때 left와 right로 갈렸기 때문에 [root.left, root.right], [root.right, root.left] 계속해서 총 4개의 값을 넣어가며 비교하면서 내려가야 한다. 

위 코드는 재귀와 스택을 활용한 풀이이다.