【LeetCode 230】二叉搜索树中第K小的元素

r囧r小猫 2022-11-30 04:03 122阅读 0赞

#### 题目描述 ####

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

#### 解题思路 ####

我们知道，二叉搜索树的左节点小于其父节点，右节点小于其右节点。这样二叉搜索树的**中序遍历就是一个从小到大的有序序列**。我们可以根据这个特性进行解答。

**递归：**

对二叉搜索树进行中序遍历，遍历的原则就是先遍历左子树，然后遍历根节点，最后遍历左子树。在遍历过程中，将遍历的结果不断存入数组中，当遍历到第k个元素的时候，就终止遍历。

递归的时间复杂度为O(n)，空间复杂度为O(n)。

**迭代：**

递归的方法也是利用的二叉搜索树的中序遍历：

*  初始化一个栈暂存树的节点
 *  先遍历根节点，再遍历左子树，并保存在栈中
 *  遍历完左子树之后，将栈中的元素的出栈，这样顺序就反过来了，变成了先成遍历的根节点，再遍历的左子树
 *  在遍历的过程中，每遍历一次k就减一
 *  遍历完左子树之后再遍历右子树
 *  不断循环，直到k为0位置，返回当前的节点值。

迭代的时间复杂度为O(n)，空间复杂度为O(n)。

#### 代码实现 ####

**递归：**

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {TreeNode} root * @param {number} k * @return {number} */
    var kthSmallest = function(root, k) { 
        const result = []
        function travel(node){ 
            if(result.length >= k) return 
            if(node.left){ 
                travel(node.left)
            }
            result.push(node.val)
            if(node.right){ 
                travel(node.right)
            }
        }
        travel(root)
        return result[k - 1]
    };

**迭代：**

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {TreeNode} root * @param {number} k * @return {number} */
    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
    }

#### 提交结果 ####

**递归：**  
![在这里插入图片描述][20200822235044585.png]  
**迭代：**  
![在这里插入图片描述][20200823001241633.png]

[20200822235044585.png]: /images/20221124/2bf6eaada4b6457e8d70bda1147f9d34.png?
[20200823001241633.png]: /images/20221124/5f835868d05f4505aa87f9214c96e1b1.png?