題目
給定一個二叉搜索樹的根節點?root?，和一個整數?k?，請你設計一個算法查找其中第?k?小的元素（從 1 開始計數）。
示例
示例 1：
輸入：root = [3,1,4,null,2], k = 1 輸出：1示例 2：
輸入：root = [5,3,6,2,4,null,null,1], k = 3 輸出：3
分析
二叉搜索樹（BST）的一個重要特性是中序遍歷的結果是一個有序序列，利用這個特性可以找出第?k?小的元素。
遞歸法
遞歸過程：
- 遞歸調用?
inorder?函數遍歷左子樹。 - 每次訪問一個節點時，
count?加 1。 - 當?
count?等于?k?時，說明找到了第?k?小的元素，將該節點的值賦給?result?并返回。 - 遞歸調用?
inorder?函數遍歷右子樹。
時間復雜度：O()，?
?是樹的高度
空間復雜度：O()
class Solution {
private:int count = 0;int result = 0;void inorder(TreeNode* node, int k) {if (!node) return;// 先遍歷左子樹inorder(node->left, k);// 計數器加 1count++;if (count == k) {result = node->val;return;}// 再遍歷右子樹inorder(node->right, k);}
public:int kthSmallest(TreeNode* root, int k) {inorder(root, k);return result;}
}; 
)
