[Leetcode/Tree] 501. Find Mode in Binary Search Tree

• mode: 최빈값

---

🔹 Binary Search Tree(이진 탐색 트리, BST)란?

 

• 이진 트리의 한 종류이며, 노드의 배치에 특정한 규칙이 적용된다:
  • 왼쪽 서브트리의 모든 값은 현재 노드보다 작아야 한다.
  • 오른쪽 서브트리의 모든 값은 현재 노드보다 커야 한다.
• 이 규칙 덕분에 탐색(검색), 삽입, 삭제 등의 연산이 효율적(평균 O(log n))으로 수행된다.

 

출처: https://yoongrammer.tistory.com/71

 

---

🔹 중위 순회(In-order Traversal)란?

이진 탐색 트리(BST)에서 중위 순회(In-order Traversal) 를 수행하면 값이 오름차순(ascending order)으로 정렬된 순서로 방문된다.

🌟 중위 순회 순서

1. 왼쪽 서브트리 탐색
2. 현재 노드 방문
3. 오른쪽 서브트리 탐색

🔹 예제 트리

아래와 같은 BST가 있다고 가정해보자.

        4
       / \
      2   6
     / \   \
    1   3   7

중위 순회(In-order Traversal) 실행 결과:

1 → 2 → 3 → 4 → 6 → 7  (오름차순)

즉, BST는 In-order Traversal을 하면 정렬된 상태로 값이 나오므로, 이전 값과 현재 값을 비교하면서 최빈값을 찾을 수 있음!

---

# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        self.current_val = None
        self.current_count = 0
        self.max_count = 0
        self.modes = []

        def inorder_traversal(node):
            if node is None:
                return
            
            # 1. 왼쪽 서브트리 탐색
            inorder_traversal(node.left)
            
            # 2.1. 현재 노드 방문
            if node.val == self.current_val:
                self.current_count += 1
            else:
                self.current_val = node.val
                self.current_count = 1
            
            # 2.2. mode(s) 갱신
            if self.current_count > self.max_count:
                self.max_count = self.current_count
                self.modes = [node.val]
            elif self.current_count == self.max_count:
                self.modes.append(node.val)
            
            # 3. 오른쪽 서브트리 탐색
            inorder_traversal(node.right)
        
        # 4. 중위 순회 시작
        inorder_traversal(root)
        return self.modes