題⽬描述

給定⼀棵⼆叉搜索樹，請找出其中的第 k ⼩的 TreeNode 結點。

示例1
輸⼊：{5,3,7,2,4,6,8},3
返回值：{4}

思路及解答

二叉搜索樹的關鍵性質

二叉搜索樹具有一個重要特性：中序遍歷（左-根-右）BST會得到一個升序排列的節點值序列。因此，尋找第k小的節點本質上就是獲取中序遍歷序列中的第k個元素。理解這一點是掌握所有解法的基石。

遞歸中序遍歷（直觀版）

算法思路：

1. 進行遞歸中序遍歷
2. 將遍歷到的節點值依次加入一個列表。
3. 遍歷完成後，列表中的元素就是升序排列的。
4. 從列表中取出第k-1個元素（索引從0開始）即為答案。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // 用於存儲中序遍歷結果的列表
        List<Integer> inorderList = new ArrayList<>();
        // 執行中序遍歷
        inorderTraversal(root, inorderList);
        // 返回第k小的元素（列表索引從0開始，所以是k-1）
        return inorderList.get(k - 1);
    }
    
    /**
     * 遞歸中序遍歷二叉樹
     * @param node 當前遍歷的節點
     * @param list 存儲遍歷結果的列表
     */
    private void inorderTraversal(TreeNode node, List<Integer> list) {
        if (node == null) {
            return; // 遞歸終止條件：遇到空節點則返回
        }
        inorderTraversal(node.left, list);  // 遞歸遍歷左子樹
        list.add(node.val);                 // 訪問當前節點，將值加入列表
        inorderTraversal(node.right, list); // 遞歸遍歷右子樹
    }
}

• 時間複雜度：O(n)。需要遍歷樹中的所有n個節點。
• 空間複雜度：O(n)。主要取決於遞歸調用棧的深度（最壞情況為O(n)，樹退化成鏈表）和存儲遍歷結果的列表（O(n)）。

迭代中序遍歷（提前終止）

方法一需要遍歷完整棵樹，即使答案在很早就已確定。我們可以利用迭代中序遍歷實現提前終止，找到第k小的節點後立即返回，提升效率。

算法思路：

1. 使用一個棧來模擬遞歸過程。
2. 從根節點開始，將所有左子節點壓入棧，直到最左邊的節點。
3. 彈出棧頂元素，這將是當前最小的節點。
4. 每彈出一個節點，計數器k減1。當k減到0時，當前節點就是第k小的節點，直接返回。
5. 如果k不為0，則轉向當前節點的右子樹，重複步驟2-4。

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        
        while (current != null || !stack.isEmpty()) {
            // 將當前節點及其所有左子節點壓入棧
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 彈出棧頂節點，即當前最小的節點
            current = stack.pop();
            k--; // 計數器減1
            // 如果k減到0，説明找到了第k小的節點
            if (k == 0) {
                return current.val;
            }
            // 轉向右子樹
            current = current.right;
        }
        // 如果k超出節點總數，返回-1（根據題目保證k有效，此情況可不處理）
        return -1;
    }
}

• 時間複雜度：最壞情況O(n)（當k=n時仍需遍歷大部分節點），平均情況優於O(n)，因為可能提前返回。
• 空間複雜度：O(h)，其中h是樹的高度。棧的深度最大為樹高，在平衡BST中為O(log n)。

記錄子節點數的遞歸（進階優化）

如果BST結構頻繁變動（插入、刪除），但需要頻繁查詢第k小的值，前兩種方法每次查詢都可能需要O(n)時間。我們可以通過擴展樹節點結構，記錄以每個節點為根的子樹中的節點個數，來優化查詢效率。

算法思路：

1. 修改樹節點結構，增加一個字段（如size）表示以該節點為根的子樹的總節點數。
2. 在插入、刪除節點時，維護每個節點的size信息。
3. 查詢第k小的節點時：
   • 從根節點開始。
   • 計算左子樹的節點數leftSize。
   • 如果k <= leftSize，説明目標節點在左子樹，遞歸地在左子樹中尋找第k小的節點。
   • 如果k == leftSize + 1，説明當前根節點就是目標節點。
   • 如果k > leftSize + 1，説明目標節點在右子樹，遞歸地在右子樹中尋找第k - (leftSize + 1)小的節點。

class TreeNodeWithSize {
    int val;
    TreeNodeWithSize left;
    TreeNodeWithSize right;
    int size; // 以該節點為根的子樹包含的節點總數

    TreeNodeWithSize(int x) {
        val = x;
        size = 1; // 初始時只有自身
    }
    
    // 假設插入操作會更新size，這裏省略具體的樹結構維護代碼
}

public class Solution {
    public int kthSmallest(TreeNodeWithSize root, int k) {
        if (root == null) {
            return -1;
        }
        // 計算左子樹的節點數（如果左子樹為空，則節點數為0）
        int leftSize = (root.left != null) ? root.left.size : 0;
        
        if (k <= leftSize) {
            // 第k小的節點在左子樹
            return kthSmallest(root.left, k);
        } else if (k == leftSize + 1) {
            // 當前節點就是第k小的節點
            return root.val;
        } else {
            // 第k小的節點在右子樹，在右子樹中尋找第 (k - (leftSize + 1)) 小的節點
            return kthSmallest(root.right, k - (leftSize + 1));
        }
    }
}