给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
= =一看就想到中序遍历
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot==null||k==0) {
return null;
} ArrayList<TreeNode> list = new ArrayList<>();
list=inOrder(list, pRoot);
//要注意这个地方越界
if(k>list.size()) {
return null;
}
return list.get(k-1);
} public ArrayList<TreeNode> inOrder(ArrayList<TreeNode> list,TreeNode pRoot){
if(pRoot==null) {
return list;
} if(pRoot.left!=null) {
list=inOrder(list, pRoot.left);
}
list.add(pRoot);
if(pRoot.right!=null) {
list=inOrder(list, pRoot.right);
}
return list;
} public static void main(String[] args) {
TreeNode n1 = new TreeNode(8);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(10);
TreeNode n4 = new TreeNode(5);
TreeNode n5 = new TreeNode(7);
TreeNode n6 = new TreeNode(9);
TreeNode n7 = new TreeNode(11);
n1.left=n2;
n1.right=n3;
n2.left=n4;
n2.right=n5;
n3.left=n6;
n3.right=n7;
new Solution().KthNode(n1, 1);
} }
二叉搜索树的第k个节点的更多相关文章
-
力扣 - 剑指 Offer 54. 二叉搜索树的第k大节点
题目 剑指 Offer 54. 二叉搜索树的第k大节点 思路1 二叉搜索树的特性就是中序遍历结果为递增序列,而题目要求的是第 k 大节点,所以就应该是要遍历结果为降序, 按照先遍历左子树.输出节点.遍 ...
-
剑指 Offer 54. 二叉搜索树的第k大节点
题目描述 给定一棵二叉搜索树,请找出其中第k大的节点. 示例1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例2: 输入: root ...
-
二叉搜索树的第K大节点
题目描述 给定一颗二叉搜索树,请找出其中的第k大的结点. 分析 对二叉搜索树进行逆向中序遍历(先右再左),则遍历序列是降序排序的,因此中序遍历一颗二叉搜索树,可以很容易的得到它的第k大的节点.使用一个 ...
-
剑指offer(62)二叉搜索树的第K个节点
题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点.例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4. 题目分析 首先,我们可以先画图.画完图后我们要想办法从 ...
-
【Offer】[54] 【二叉搜索树的第k小节点】
题目描述 思路分析 测试用例 Java代码 代码链接 题目描述 给定一棵二叉搜索树,请找出其中第k小的节点.例如,在下图的二叉搜索树里,按节点数值大小顺序,第三小节点的值是4.  牛客网刷题地址 思 ...
-
64.二叉搜索树的第K个节点
题目描述: 给定一棵二叉搜索树,请找出其中的第k小的结点.例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4. 思路分析: 根据二叉搜索树的特殊性,我们中序遍历它 ...
-
每日一题 - 剑指 Offer 54. 二叉搜索树的第k大节点
题目信息 时间: 2019-07-04 题目链接:Leetcode tag:二叉搜索树 中序遍历 递归 难易程度:中等 题目描述: 给定一棵二叉搜索树,请找出其中第k大的节点. 示例1: 输入: ro ...
-
《剑指offer》面试题54. 二叉搜索树的第k大节点
问题描述 给定一棵二叉搜索树,请找出其中第k大的节点. 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2: 输入: ...
-
剑指offer——59二叉搜索树的第k大节点
题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点.例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4. 题解: 考察的就是中序遍历 不过注意进行剪枝 cl ...
随机推荐
-
java 多线程(wait/notify/notifyall)
package com.example; public class App { /* wait\notify\notifyAll 都属于object的内置方法 * wait: 持有该对象的线程把该对象 ...
-
在 Win10 命令行使用 Consolas + 微软雅黑
这个过程挺神奇的,步骤参考了下面两篇文章,但是过程很曲折: 1. 使用Monaco和微软雅黑字体美化cmd和PowerShell 2. [zz]Windows的cmd.exe使用consolas加中文 ...
-
夺命雷公狗—angularjs—3—表单验证的高级用法
其实我们的angularjs都是是块状代码,其实是可以在实际开发中保存下来以后就可以达到重复利用的目的了.. 废话不多说,直接上代码: <!doctype html> <html l ...
-
tuple解包给类的构造函数
首先我们的第一步当然是将tuple解包.tuple提供了一个get函数来获取第N个元素.例如: get<1>(make_tuple(...)); 要将一个tuple全部拆解,就可以使用通过 ...
-
git创建分支与合并分支
git branch myfeture 创建分支 git checkout myfeture git add --all git commit -m git push origin myfeture ...
-
AngularJS实现的自定义过滤器简单示例
本文实例讲述了AngularJS实现的自定义过滤器.分享给大家供大家参考,具体如下: 1.自定义限制字数的过滤器 啥也不说了直接上代码吧 ? 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
-
第 9 章 数据管理 - 075 - 配置 VirtualBox backend
配置 VirtualBox backend 在 VirtualBox 宿主机上启动 vboxwebsrv 服务: C:\Program Files\Oracle\VirtualBox > VBo ...
-
install chrome and chrome driver on ubuntu
sudo apt install python-minimal # python 2.7.xsudo apt install python-pip # https://www.ubuntuupdate ...
-
Adobe reader multiple languages pack
用户打开客户发过来的PDF文档,显示不正常,这是电脑的Adobe Reader缺少相关的字体. 可以从下面地址下载相对版本的字体包安装:http://supportdownloads.adobe.co ...
-
php的opcache缓存扩展
opcache (全程 zend opcache): 从php5.5开始,默认提供的php脚本缓存扩展,编译php5.5时加上参数--enable-opcache就可以编译opcache了,只是要启用 ...