LeetCode 230: BST에서 K번째 작은 요소 — 단계별 시각적 추적

Source: Dev.to

Problem Description

이진 탐색 트리(BST)에서 k번째로 작은 요소를 찾으세요. k는 1부터 시작하는 인덱스입니다. 모든 노드를 오름차순으로 정렬했을 때 k번째 작은 노드의 값을 반환해야 합니다.

Approach

이 솔루션은 BST의 중위 순회(inorder traversal) 를 이용합니다. 중위 순회는 자연스럽게 노드를 오름차순으로 방문합니다. 왼쪽 서브트리를 재귀적으로 순회하고, 현재 노드를 처리한 뒤, 오른쪽 서브트리를 순회하면서 모든 값을 정렬된 리스트에 모은 뒤 k번째 요소를 반환합니다.

Complexity

• 시간: O(n)
• 공간: O(n)

Code

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder_traversal(node):
            if not node:
                return []

            left = inorder_traversal(node.left)
            right = inorder_traversal(node.right)

            return left + [node.val] + right

        inorder_values = inorder_traversal(root)
        return inorder_values[k - 1]

Interactive Visualization

TraceLit을 열어 보세요 — LeetCode 연습을 위한 시각적 알고리즘 트레이서.