?

給定一個二叉搜索樹，編寫一個函數?kthSmallest?來查找其中第?k?個最小的元素。

說明：
你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。

示例 1:

輸入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
? 2
輸出: 1
示例 2:

輸入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
輸出: 3

//二叉樹的中序遍歷 //左，根，右 class Solution { public:int kthSmallest(TreeNode* root, int k) {if(root==NULL) return 0;int res=0,i=1;stack<TreeNode*> s;TreeNode* p=root;//根節點入棧s.push(root);while(!s.empty()){while(p&&p->left){p=p->left;s.push(p);}p=s.top();s.pop();if(i==k) {res=p->val;break;}i++;p=p->right;if(p) s.push(p);}return res;} };

利用了二叉搜索樹的性質，中序遍歷時有序的

?

?代碼地址：https://www.cnblogs.com/joelwang/p/10919603.html

?

總結

以上是生活随笔為你收集整理的小米面试：二叉搜索中第K小的元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。