腾讯&leetcode230:二叉搜索树中第K小的元素
sisterAn opened this issue · 3 comments
sisterAn commented
给定一个二叉搜索树,编写一个函数 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 函数?
附赠leetcode地址:leetcode
sisterAn commented
在 前端进阶算法11:二叉查找树(BST树) 中我们知道:中序遍历其实是对🌲进行排序操作 ,并且是按从小到大的顺序排序,所以本题就很简单了
解题思路: 中序遍历二叉搜索树,输出第 k 个既可
代码实现(递归):
const kthSmallest = function(root, k) {
let res = null
let inOrderTraverseNode = function(node) {
if(node !== null && k > 0) {
// 先遍历左子树
inOrderTraverseNode(node.left)
// 然后根节点
if(--k === 0) {
res = node.val
return
}
// 再遍历右子树
inOrderTraverseNode(node.right)
}
}
inOrderTraverseNode(root)
return res
}
复杂度分析:
- 时间复杂度:O(k)
- 空间复杂度:不考虑递归栈所占用的空间,空间复杂度为 O(1)
代码实现(迭代):
const 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
}
复杂度分析:
- 时间复杂度:O(H+K)
- 空间复杂度:空间复杂度为 O(H+K)
AnranS commented
var kthSmallest = function(root, k) {
let current = root;
let stack = [];
let index = 0;
while(current) {
stack.push(current);
current = current.left;
}
while(stack.length) {
index++;
let node = stack.pop();
if(index === k) return node.val;
if(node.right) {
current = node.right;
while(current) {
stack.push(current);
current = current.left;
}
}
}
};
Forever17s commented
栈 + 中序遍历
var kthSmallest = function(root, k) {
let cur = 0
const stack = []
const helper = (node) => {
if(!node) return
helper(node.left)
if(cur ++ >= k) return
stack.push(node.val)
helper(node.right)
}
helper(root)
return stack.pop()
};