我要招人

去企业版

首页 > 试题广场 >

二叉搜索树的第k个节点

[编程题]二叉搜索树的第k个节点

热度指数：60977 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

数据范围： $0 \le n \le1000$ ， $0 \le k \le1000$ ，树上每个结点的值满足 $0 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

示例1

输入

{5,3,7,2,4,6,8},3

输出

示例2

输入

{},1

输出

-1

备注:

当树是空

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2022-04-25 17:46:12

精华题解题目主要信息：给定一棵节点数为n二叉搜索树，需要其中的第k小的节点值返回第k小的节点值即可不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样举一反三：学习完本题的思路你可以解决如下题目： JZ68. 二叉搜索树的最近公共祖先 JZ8. 二叉树展开全文

每天学习一点

发表于 2021-11-25 15:37:06

由于是二叉搜索树，采用中序遍历得到的第k个节点即第k小的值，判断输出是否是第k个就可以返回值了，使用栈来辅助遍历 /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode rig 展开全文

蓉城小晋

发表于 2021-11-23 22:12:15

```/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可展开全文

有pp才有真相

发表于 2022-01-07 15:44:16

1 总结难点基础中序还得反复联系 C++ stl申明风格和 Java 数据机构申明混淆了，两个stack有质的区别不然反复报 type conversion错误 http://www.cplusplus.com/reference/stack/stack/push/ 请利用好基础代码框架展开全文

想吃火锅的火龙果在吐槽

发表于 2021-11-19 18:22:21

看到没人写题解，小透明写一下吧。用的是中序遍历，做法不怎么优美，但也算解出来了。 public class Solution { int x; TreeNode res = null; public TreeNode KthNode (TreeNode proot, int k) { // 展开全文

fred-coder

发表于 2021-11-24 00:49:17

由于是二插搜索树，进行中序遍历得到有序数组，再对特殊值进行判断 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right 展开全文

WANGwww

发表于 2022-02-22 13:13:01

解题思路 ①二叉搜索树排序 ②按照数组索引，直接返回第k小数值 ③注意特殊情况（空树、k大于树数量...）的处理 /* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null 展开全文

牛客264578000号

发表于 2022-02-15 00:18:48

/** struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; C语言声明定义全局变量请加上static，防止重复定义 / /* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值展开全文