MediumRating 1401
230. Kth Smallest Element in a BST
treedepth-first-searchbinary-search-treebinary-tree
解題說明
Kth Smallest Element in a BST
題目描述：在二元搜尋樹中找到第 k 小的元素。
解題思路：BST 的中序遍歷產生嚴格遞增序列。進行中序遍歷（左-根-右），計數訪問的節點，第 k 個訪問的節點即為答案。可用迭代（Morris 遍歷達到 O(1) 空間）或遞迴實現。
C++ 解法
複雜度分析
時間複雜度：O(h + k)，h 為樹高 — 先走到最左，再計 k 個節點。
空間複雜度：O(h) — 迭代棧深度等於樹高。
虛擬碼
1. Iterative in-order traversal: 2. Push all left children onto stack 3. Pop node, decrement k 4. If k == 0: return node.val 5. Move to right subtree, repeat
其他解法
中序遍歷全收集 O(n) 時間，O(n) 空間：遍歷整棵樹至陣列，取第 k 個 — 時間複雜度更差，空間無優化。
迭代中序遍歷 O(k) 時間，O(h) 空間：本解法，維護堆疊逐一彈出 k 個 — 此即標準。
延伸思考
- 如何找第 k 大的元素？
- 若樹頻繁修改，如何優化查詢？
- 若樹非常大不在記憶體中？