小米面试：二叉搜索中第K小的元素

 

给定一个二叉搜索树，编写一个函数 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小的元素的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。