题目:给定一棵二叉搜索树,请找出其中第k大的节点。
这道题是一道简单题,刚开始写的时候没看到是二叉搜索树,所以当成二叉树来做了,代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthLargest(TreeNode root, int k) {
List<Integer> list = new ArrayList<Integer>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null) return 0;
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
Collections.sort(list);
return list.get(list.size()-k);
}
}
虽然通过了,但是分数不高,然后重新优化了一下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> list = new ArrayList<Integer>();
public int kthLargest(TreeNode root, int k) {
midSort(root);
return list.get(list.size()-k);
}
public void midSort(TreeNode root){
if(root == null) return;
midSort(root.left);
list.add(root.val);
midSort(root.right);
}
}
我的思路就是先遍历,然后找出数组第k大的,这题主要考的就是二叉搜索树的中序遍历。
本文地址:https://blog.csdn.net/weixin_40392620/article/details/107332126
如对本文有疑问, 点击进行留言回复!!
springcloud中feign调用处理mybatis-plus Ipage反序列化问题。
Flume 史上最全面的大数据学习第十篇(一) 别再说不知道flume是什么了
网友评论