[LeetCode 풀이/python] 101. Symmetric Tree (easy)

문제 설명: 이진트리 root 가 주어졌을 때, 해당 트리가 자기 자신의 거울인지 (i.e. 중심을 기준으로 대칭인지) 확인하시오.

 

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

 

예시 1)

입력: root = [1, 2, 2, 3, 4, 4, 3]  -->  출력: true

 

예시 2)

입력: root = [1, 2, 2, null, 3, null, 3]  -->  출력: false

 

제한 조건:

• 트리의 노드 개수는 [1, 1000] 의 범위 내에 있음
• -100 <= node.val <= 100

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • tree 전체 (linked list) 를 입력으로 받는 함수 isSymmetric 와 별도로 트리의 좌/우를 비교하기 위한 별도의 함수 check_symm 을 정의하여 활용
  • 함수 check_symm 은 현 노드 기준 두 자식 노드 left, right 을 입력으로 받아 조건에 따라 true / false 를 비교 결과로 리턴함
    • left, right 모두 None 인 경우, 해당 노드는 leaf 에 해당하며 두 자식 노드 모두 None 으로 동일하므로 symmetric 함
    • left, right 중 어느 한쪽만 None 인 경우, symmetric 하지 않으므로 false 를 리턴함
    • left, right 모두 존재하며 값이 같을 경우 (symmetric), 이들의 자식들에 대해서는 inner / outer pair 를 구분하여 대칭 여부를 recursively 비교함  -->  inner, outer 모두 True (symmetric) 일 경우에만 true 리턴함

 

• 코드 구현

# 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: TreeNode) -> bool:
        if not root:
            return False
        else:
            return self.check_symm(root.left, root.right)
            
    def check_symm(self, left, right):
        if (not left) and (not right):  ## leaf
            return True
        elif (not left) or (not right):  
            return False
        
        if left.val == right.val:
            inner = self.check_symm(left.right, right.left)
            outer = self.check_symm(left.left, right.right)
            return (inner and outer)
        else:
            return False

 

• 결과
  • 이진트리이고, 각 level 에 대해 O(1) 의 시간복잡도를 가지므로 총 O(d) = (log n) 소요됨
  • 연결 리스트 / 트리 구조를 다루는 데에 아직 어려움이 있음....ㅠ_ㅠ 풀다보면 익숙해지려나.......ㅠ_ㅠ