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

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   on Jul 21, 2020
2. sisterAn commented on Jul 21, 2020

   

   sisterAn

   on Jul 21, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   在 前端进阶算法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
3. AnranS commented on Nov 20, 2020

   

   AnranS

   on Nov 20, 2020

   More actions

   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;
               }
           }
       }
   };
4. Forever17s commented on Feb 28, 2021

   

   Forever17s

   on Feb 28, 2021

   More actions

   栈 + 中序遍历

   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()
   };
5. AlexZhang11 commented on Jun 6, 2024

   

   AlexZhang11

   on Jun 6, 2024

   More actions

   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))