腾讯&leetcode230：二叉搜索树中第K小的元素

[sisterAn]

给定一个二叉搜索树，编写一个函数 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]

在 前端进阶算法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)

leetcode

[AnranS]

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]

栈 + 中序遍历

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()
};

[AlexZhang11]

let root5 ={
 val:5,
 left:{
 val:3,
 left:{
 val:2,
 left:{
 val:1,
 left:null,
 right:null
 },
 right:null
 },
 right:{
 val:4,
 left:null,
 right:null
 }
 },
 right:{
 val:6,
 left:null,
 right:null
 }
}
function getKMin(root,k){
 let stack = []
 let cur = root
 let result = []
 while(cur||stack.length){
 while(cur){
 stack.push(cur)
 cur = cur.left
 }
 let top = stack.pop()
 result.push(top.val)
 cur = top.right
 }
 return result[k-1]
}

console.log(getKMin(root5,3))