Open xszi opened 3 years ago
中序遍历二叉搜索树,输出第 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
}
迭代实现
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
}
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明: 你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
输出: 3
进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?
leetcode