BST의 root와 k가 주어졌을 때,
트리에서 k번째로 작은 값을 리턴하는 문제이다.
(1-indexed: 1부터 시작하는 인덱스 기준)
풀이 1: 브루트포스(DFS) - O(n log n)
가장 간단한 풀이로는 dfs를 통해 완전 탐색을 하고, 정렬하여 k번째로 작은 값을 리턴할 수 있다.
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
arr = []
def dfs(node):
if not node:
return
arr.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
arr.sort()
return arr[k - 1]트리의 모든 노드를 한번씩 방문하는 dfs는 O(n)이지만,
arr.sort()는 Timsort를 사용하고 평균(최악)의 경우 O(n log n)이기 때문에
시간 복잡도는 O(n log n)이다.
중위 순회 (Inorder Traversal)와 이진 탐색 트리(BST)
중위 순회는 이진 트리의 순회 방식 중 하나로, 왼쪽 -> 현재 -> 오른쪽 순서로 탐색하는 방법이다.
BST는 왼쪽 서브트리의 모든 값은 현재 노드보다 작고, 오른쪽 서브트리의 모든 값은 현재 노드보다 크다.
따라서 BST에서 중위 순회를 수행하면 값이 자동으로 오름차순으로 정렬된다.
풀이 2: DFS (Inorder Traversal)
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
arr = []
def dfs(node):
if not node:
return
dfs(node.left) # 왼쪽 서브트리 탐색
arr.append(node.val) # 현재 노드 값 추가
dfs(node.right) # 오른쪽 서브트리 탐색
dfs(root)
return arr[k - 1]풀이 1의 코드를 약간만 바꾼 풀이 2를 보자.
dfs에서 왼쪽 -> 현재 -> 오른쪽 순서로 모든 노드를 정확히 한번씩 방문하게 되므로 O(n)의 시간이 걸리며
k번째 원소 접근에도 O(1)의 시간이 걸리므로
최종 시간복잡도는 O(n)이다.
풀이 3 - 스택과 Iterative(반복문)을 활용한 Inorder Traversal
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
cur = root
while stack or cur:
while cur: # 왼쪽 서브트리 탐색 (최소값을 찾기 위해)
stack.append(cur)
cur = cur.left
cur = stack.pop() # 가장 왼쪽에 있는 노드 가져옴(가장 작은 값)
k -= 1
if k == 0: # k번째 노드라면 값 반환
return cur.val
cur = cur.right # 오른쪽 서브트리 탐색중위 순회를 위한 스택을 만들고, cur에 현재 노드를 저장한다.
스택이 비어있지 않거나, 방문할 노드가 남아있을 때까지 while문을 통해 반복한다.
왼쪽 -> 현재 노드 -> 오른쪽 순서로 중위 순회를 진행한다.
재귀는 함수 호출 스택을 사용하므로 트리의 높이만큼 함수 호출이 스택에 쌓이게 된다.
반면 Iterative(반복문) 방식은 명시적인 스택을 활용하므로,
특히 깊이가 깊은 트리에서 재귀보다 메모리를 절약할 수 있다.
