題目
#

leetcode 230 - Kth Smallest Element in a BST (題目說明請點連結)

題目簡述
#

給一個二元搜尋樹（Binary Search Tree）的根節點 root 和一個整數 k，請找出其中第 k 小的元素值。
注意：假設 k 總是有效的，即 1 ≤ k ≤ 節點總數。

範例
#

Example 1:

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

graph TD; A[3] B[1] C[4] D[null] E[2] A --> B A --> C B --> D B --> E

Example 2:

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

graph TD; A[5] B[3] C[6] D[2] E[4] F[null] G[null] H[1] A --> B A --> C B --> D B --> E C --> F C --> G D --> H

解題思路
#

這題要求我們在二元搜尋樹（BST）中找到第 k 小的元素。由於 BST 的特性，中序遍歷（Inorder Traversal）會按照升序順序訪問所有節點。因此，我們可以使用中序遍歷來找到第 k 小的元素。

解法
#

使用中序遍歷來訪問 BST 中的所有節點
維護一個計數器 cnt，記錄當前訪問的節點數量
當計數器等於 k 時，記錄當前節點的值
返回第 k 小的元素值

步驟
#

初始化：
- 設定計數器 cnt = 0
- 設定結果變數 res = 0
中序遍歷：
- 遞迴訪問左子樹
- 訪問當前節點，計數器加 1
- 如果計數器等於 k，記錄當前節點值並返回
- 遞迴訪問右子樹
返回結果：
- 返回記錄的第 k 小元素值

例子說明
#

root = [3,1,4,null,2], k = 1

graph TD; A[3] B[1] C[4] D[null] E[2] A --> B A --> C B --> D B --> E

步驟	當前節點	計數器 cnt	節點值	是否為第 k 小	說明
初始化	-	0	-	-	開始中序遍歷
第 1 步	1	1	1	是（k=1）	訪問最左節點，計數器為 1
第 2 步	2	2	2	否	訪問節點 1 的右子節點
第 3 步	3	3	3	否	訪問根節點
第 4 步	4	4	4	否	訪問根節點的右子節點

最終結果： 1

中序遍歷順序說明：

中序遍歷順序：1 → 2 → 3 → 4
第 1 小元素：1（第一個訪問的節點）
第 2 小元素：2（第二個訪問的節點）
第 3 小元素：3（第三個訪問的節點）
第 4 小元素：4（第四個訪問的節點）

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int cnt = 0;    // 計數器，記錄當前訪問的節點數量
    int res = 0;    // 結果變數，儲存第 k 小的元素值
    
    public int kthSmallest(TreeNode root, int k) {
        // 開始中序遍歷，尋找第 k 小的元素
        inorder(root, k);
        return res;
    }

    // 中序遍歷方法
    public void inorder(TreeNode node, int k){
        // 邊界條件：如果節點為空，直接返回
        if(node == null) {
            return;
        }

        // 遞迴訪問左子樹
        inorder(node.left, k);
        
        // 訪問當前節點，計數器加 1
        cnt++;
        
        // 如果計數器等於 k，記錄當前節點值並返回
        if(cnt == k){
            res = node.val;
            return;
        }
        
        // 遞迴訪問右子樹
        inorder(node.right, k);
    }
}

時間複雜度
#

時間複雜度：O(k)，其中 k 是要找的第 k 小元素的位置
- 最壞情況下需要訪問 k 個節點才能找到第 k 小的元素
- 如果 k 接近節點總數 n，則時間複雜度接近 O(n)
空間複雜度：O(h)，其中 h 是樹的高度
- 遞迴調用棧的深度等於樹的高度
- 最壞情況下（樹為線性結構），空間複雜度為 O(n)