[BST*]99클럽 코테 스터디 14일차 TIL + 0101-symmetric-tree

101. Symmetric Tree

Easy

---

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 is_mirror(t1,t2):
            if not t1 and not t2:
                return True
            elif not t1 or not t2:
                return False
            
            return (t1.val == t2.val and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left))
        
        # base-condtion
        if not root:
            return True
        # recursirve-case    
        return is_mirror(root.left, root.right)

1. 어제와 비교

- 이진트리 탐색을 재귀적으로 구현하기

두개 다 조건문으로 분기하면서 재귀적으로 트리 탐색을 하였음

 

- 탐색 방식의 변화

어제의 경우 찾고자 하는 수와 비교를 하면서 찾았다면, 오늘은 한쪽트리는 left, 다른쪽은 right를 하면서 서로가 같은지 검증하는것임

 

2. 헤맨부분

- 재귀 구현방법

isSymmetric() 을 재귀호출하는것이 아니라, 별도의 새로운 함수를 만들어 이 함수를 재귀하는 방법으로 구현해야함

 

- 서로간에 같은지 검증방법

단순히 거울처럼 검증하는 곳 외에, 두개의 노드중 하나는 None 이고 다른곳은 None 이 아닐때 False인데 이것을 and 와 or 조건으로 만든것을 배웠음

 

 

<모범사례>

- 상동

 

<보충학습>

1. 재귀함수 정의 및 호출방법!

def function_name(params):
    if base_condition:
        return result
    return function_name(modified_params)

basecase 와 recursivecase 두가지를 하는방법을 잊지말기

 

2. 재귀함수 유의점

 

깊은 트리구조에서는 재귀호출로인한 스택오버플로우 유의하기

 

3. 용도

 

대싱성을 잊지말기 (UI 대칭 / 그래픽스 대칭 / 자료구조 대칭 / 네트워크 디자인)

실무에서는 내용 대칭성 보다 구조적 대칭성을 확인이 더 빈번함

이렇게 하면 연산의 효율성이 높아짐 (병목등이 줄어들어서)