1. 题目描述
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?
2. 解题思路
我们知道,二叉搜索树的左节点小于其父节点,右节点小于其右节点。这样二叉搜索树的中序遍历就是一个从小到大的有序序列。我们可以根据这个特性进行解答。
递归:
对二叉搜索树进行中序遍历,遍历的原则就是先遍历左子树,然后遍历根节点,最后遍历左子树。在遍历过程中,将遍历的结果不断存入数组中,当遍历到第k个元素的时候,就终止遍历。
递归的时间复杂度为O(n),空间复杂度为O(n)。
迭代:
递归的方法也是利用的二叉搜索树的中序遍历:
- 初始化一个栈暂存树的节点
- 先遍历根节点,再遍历左子树,并保存在栈中
- 遍历完左子树之后,将栈中的元素的出栈,这样顺序就反过来了,变成了先成遍历的根节点,再遍历的左子树
- 在遍历的过程中,每遍历一次k就减一
- 遍历完左子树之后再遍历右子树
- 不断循环,直到k为0位置,返回当前的节点值。
3. 代码实现
递归:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
const result = []
function travel(node){
if(result.length >= k) return
if(node.left){
travel(node.left)
}
result.push(node.val)
if(node.right){
travel(node.right)
}
}
travel(root)
return result[k - 1]
};
迭代:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
let kthSmallest = function(root, k) {
let stack = []
let node = root
while(node || stack.length) {
// 遍历左子树
while(node) {
stack.push(node)
node = node.left
}
node = stack.pop()
if(--k === 0) {
return node.val
}
node = node.right
}
return null
}
4. 提交结果
递归:
迭代: