230. Kth Smallest Element in a BST

Medium
Description

給定一棵 BST 的根節點和整數 k，回傳 BST 中第 k 小的元素（1-indexed）。

Example:

Input: root = [3,1,4,null,2], k = 1 Output: 1

Intuition#

BST 中序遍歷是有序的，第 k 個被訪問的節點就是答案。

  • 中序遍歷 BST 得到遞增序列，遍歷到第 k 個就可以提前停止
  • 不需要真的收集所有元素，用計數器即可

Approaches#

1: 中序遍歷收集全部元素#

  • 概念: 完整中序遍歷收集所有值到列表，回傳第 k-1 個元素
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val list = mutableListOf<Int>()
        inorder(root, list)
        return list[k - 1]
    }

    private fun inorder(node: TreeNode?, list: MutableList<Int>) {
        if (node == null) return
        inorder(node.left, list)
        list.add(node.`val`)
        inorder(node.right, list)
    }
}

⭐ 2: 中序遍歷 + 提前停止（Iterative）#

  • 概念: 迭代式中序遍歷，計數到 k 就立即回傳
  • 時間複雜度: O(h + k)，h 為樹高
  • 空間複雜度: O(h)
class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val stack = ArrayDeque<TreeNode>()
        var current = root
        var count = 0
        while (current != null || stack.isNotEmpty()) {
            while (current != null) {
                stack.addLast(current)
                current = current.left
            }
            current = stack.removeLast()
            count++
            if (count == k) return current.`val`
            current = current.right
        }
        return -1 // 不會到達
    }
}
迭代式中序遍歷模板

迭代式中序遍歷的核心模式：

  1. 先一路往左走到底，把沿途節點推入堆疊
  2. 彈出堆疊頂端（當前最小未處理節點）
  3. 處理該節點
  4. 轉向右子樹，重複步驟 1

這個模板可以用在很多 BST 問題上。

🔑 Takeaways#

  • Pattern: BST + 中序遍歷 = 有序序列，第 k 小/大問題直接解決
  • 關鍵技巧: 迭代式中序遍歷可以在找到答案後提前停止，比遞迴更容易控制提前終止