qappleh
commented
3 years ago 解题思路： 中序遍历二叉搜索树，输出第 k 个既可
代码实现（递归）：
let 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)
代码实现（迭代）：
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
}
复杂度分析：
- 时间复杂度：O(H+K)
- 空间复杂度：空间复杂度为 O(H+K)
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
示例 2:
进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
附赠leetcode地址：leetcode