99클럽 코테 스터디 14일차 TIL (Symmetric Tree) - LeetCode

1. 오늘의 학습 키워드

• 트리
• 이진트리

---

2. 문제: 101. Symmetric Tree

• 단계: Easy
• 출처: https://leetcode.com/problems/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

---

3. 나의 풀이

접근 방법

문제 제목 그대로 대칭이 이뤄지는지를 확인하면 되는 문제이다.

맨 위의 root 노드를 기준으로 아래 왼쪽, 오른쪽 서브 트리가 대칭을 이루는지를 확인하면 된다. 그렇다면! 재귀를 활용하여 반복적으로 검사하면 되지 않을까?

조건은 3가지가 있을 것이다.

1. root 노드의 왼쪽, 오른쪽 노드가 둘 다 없는 경우
2. root 노드의 왼쪽, 오른쪽 중 하나가 있는 경우
3. 둘 다 있는 경우

코드를 보면 아래와 같다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isSubtreeSymmetric(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 isSubtreeSymmetric(left.left, right.right) and isSubtreeSymmetric(left.right, right.left)
        
        return isSubtreeSymmetric(root,root)

마지막 조건인 root 노드의 왼쪽, 오른쪽 노드 (서브트리)가 있으면, 루트 노드의 왼쪽 노드, 오른쪽 노드가 같아야 하고, root 노드의 왼쪽 노드의 왼쪽 노드와 root 노드의 오른쪽 노드의 오른쪽 노드가 같아야 하고, root 노드의 왼쪽 노드의 오른쪽 노드와 root 노드의 오른쪽 노드의 왼쪽 노드가 같아야 한다.

트리의 길이는 알 수 없으므로 위 내용을 재귀적으로 반복해야 한다.

---

4. 결과

https://leetcode.com/problems/symmetric-tree/submissions/1347870436

---

5. 결론

keep going!

읽어주셔서 감사합니다!