日籍商人被捕,燕福龙有两个女儿,新视野影院
给定一个二叉搜索树，编写一个函数 kthsmallest 来查找其中第 k 个最小的元素。
须知：二叉搜索树，又叫二叉排序树，二叉查找树。特点是：左子树的所有元素都小于等于根节点，右子树的所有节点都大于等于根节点。并且，二叉搜索树的中序遍历是升序排列的。
自己的思路：刚开始不知道二叉搜索树的性质；自己采用了优先队列的方式：
我要评论 public int kthsmallest(treenode root, int k){
priorityqueue<integer> pqueue = new priorityqueue<integer>((s1,s2)->s2-s1);
queue<treenode> queue = new linkedlist<>();
queue.add(root);
while (!queue.isempty()){
treenode node = queue.poll();
pqueue.add(node.val);
if (pqueue.size()>k){
pqueue.poll();
}
if (node.left != null){
queue.add(node.left);
}
if (node.right!=null){
queue.add(node.right);
}
}
return pqueue.poll();
}
但是效率并不好。
之后利用二叉搜索树的性质可以加快查找：利用栈来添加和移除元素。
public int kthsmallest2(treenode root, int k){
linkedlist<treenode> stack = new linkedlist<>();
while (true){
while (root!=null){
stack.add(root);
root = root.left;
}
root = stack.removelast();
if (--k==0) return root.val;
root = root.right;
}
}
复杂度分析
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论