二叉搜索树的第k大节点(剑指offer 54)Java中序遍历
2023-03-14 22:54:20 时间
一、题目描述
给定一棵二叉搜索树,请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 4
限制:
1 ≤ k ≤ 二叉搜索树元素个数
二、思路讲解
因为二叉搜索树的中序遍历为递增数列。
所以我们只需中序遍历一遍,然后输出索引为size-k的值(第k打)即可。
三、Java代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private static List<Integer> list = new ArrayList<Integer>(); public int kthLargest(TreeNode root, int k) { zhongxu(root); return list.get(list.size()-k); } public static void zhongxu(TreeNode node){ if(node == null){ return; } zhongxu(node.left); list.add(node.val); zhongxu(node.right); } }
四、时空复杂度分析
时间复杂度: O(N) 考虑最差情况,当树退化为链表时,递归深度为N
空间复杂度: O(N)
五、代码优化
二叉搜索树的中序遍历为递增序列,那么中序遍历的逆序为递减序列。如果我们逆序中序遍历,那么在遍历到第k个值时就可以提前退出了,而无需遍历整棵树。
相关文章
- Java要抛弃祖宗的基业,Java程序员危险了!
- 十大 Java 语言特性
- JVM 三色标记算法,原来是这么回事!
- 聊聊 Spring 事务控制策略以及 @Transactional 失效问题避坑
- 写给 Java 程序员的前端 Promise 教程
- 写给 Java 程序员的前端 Promise 教程,你学会了吗?
- Java 中为什么不全部使用 Static 方法?
- Java 池化技术你了解多少?
- Java 服务 Docker 容器化优秀实践
- Spring Boot + EasyExcel导入导出,简直太好用了!
- 我们一起聊聊 Java 内存泄漏
- CentOS 下安装 Docker 极简教程
- JDK 19 功能集冻结:Java 19 只有七个新特性
- 关于 CMS 垃圾回收器,你真的懂了吗?
- 为什么会有这么多编程语言?
- 改善Java代码的八个建议
- 接口流量突增,如何做好性能优化?
- Java 以编程方式创建JAR文件
- POJO、Java Bean是如何定义的
- Spring 的 Bean 明明设置了 Scope 为 Prototype,为什么还是只能获取到单例对象?