给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。
示例 1:

例
输入:root = [3,1,4,null,2], k = 1
输出:1
示例 2:

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3
 例

 
提示:

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

思路:
因为给定的是一颗二叉搜索树,所以中序遍历即为顺序排序。我们运用非递归的中序遍历,构造队列,在出队时访问即为中序遍历,我们只需要在出队时队k进行判断就可以了,当k为0时返回root的值即为所得。

Last modification:October 25th, 2021 at 07:51 pm
如果觉得我的文章对你有用,请随意赞赏