給定一個二叉搜索樹的根節點?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

提示：

• 樹中的節點數為?n?。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

思路和算法

因為二叉搜索樹和中序遍歷的性質，所以二叉搜索樹的中序遍歷是按照鍵增加的順序進行的。于是，我們可以通過中序遍歷找到第 k 個最小元素。

「二叉樹的中序遍歷」可以參考「94. 二叉樹的中序遍歷的官方題解」，具體地，我們使用迭代方法，這樣可以在找到答案后停止，不需要遍歷整棵樹。

代碼

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> stk;while(root != nullptr || !stk.empty()){while(root != nullptr){stk.push(root);root = root -> left;}root = stk.top();stk.pop();--k;if(k == 0){break;}root = root -> right;}return root -> val;}
};