題目描述:在二元搜尋樹中找到第 k 小的元素。
解題思路:BST 的中序遍歷產生嚴格遞增序列。進行中序遍歷(左-根-右),計數訪問的節點,第 k 個訪問的節點即為答案。可用迭代(Morris 遍歷達到 O(1) 空間)或遞迴實現。
時間複雜度: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 個 — 此即標準。