LEETCODE 230. Kth Smallest Element in a BST 解题思路分析

题目大意:

二叉搜索树中第K小的元素

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 个最小的元素。

说明:
你可以假设 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 函数?


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=230

解题思路分析:

看到BST二叉搜索树的题目,我们要想到题目多数情况下是在考察二分查找的逻辑。也就是说我们算法的时间复杂度尽量要压缩在logn级别才可以。对于本题我们需要使用二分查找的方式,找到第k小的元素在哪里,我们可以将所有数字分为三个部分:左子树,当前节点,右子树。根据BST的特性可得出,左子树中所有节点一定小于当前节点,当前节点一定小于右子树中所有节点,因此我们只要知道三个部分的节点个数,那么我们就可以很容易的判断出k在哪个部分之中,如果k在中间部分(当前节点)的话,那么当前节点即是返回值。除此之外,将问题递归至子问题即可。

具体解题思路:

  1. 将当前节点分为3个部分:左子树,当前节点,右子树。
  2. 要寻找第k小的节点,那么我们先查看左子树中的节点数leftCount,如果leftCount大于等于k,说明第k小的元素在左子树中,我们递归至左子树。反之如果左子树中节点数leftCount小于k,那么说明第k小的数字不在左子树,这时将k减去leftCount。
  3. 接下来查看当前节点,如果此时k等于1,那么说明结果一定是当前节点,话句话说,除了左子树中的数字之外,当前节点的数字一定是最小的。(左子树的节点个数已在上一步骤中消耗掉)反之,如果k大于1,那么我们将k减去1。
  4. 最后再查看右子树,此时的k值与最初时相比已经发生两次变化 k1=k-leftCount-1; 我们将此时的k值称之为k1,目前为止,我们已知第k小的元素一定存在于右子树中,实际上也就是求右子树中第k1小的元素(递归至右子树)。
  5. 求某个节点下总节点数的方法也不难,只要dfs递归一下所有节点即可,具体实现可参照代码。

实现代码:

public int kthSmallest(TreeNode root, int k) {
    if(root.left!=null){ // 左子节点不为空
        // 统计左子树节点个数
        int leftCount=count(root.left);
        if(k<=leftCount){ // 如果节点个数大于等于k
             // 说明第k小的元素在左子树中,递归至左子树
            return kthSmallest(root.left, k);
        }else{
            // 反之将k减去左子树节点个数
            k-=leftCount;
        }
    }
    // 如果k等于1,当前节点即是返回结果
    if(k==1) return root.val;
    // 反之将k减去1
    else k-=1;
    // 这时第k小元素一定在右子树,递归至右子树
    return kthSmallest(root.right, k);
}
// 统计root节点下节点个数
int count(TreeNode root){
    int res=1; // 当前节点个数
    if(root.left!=null) // 累加左子树节点个数
        res+=count(root.left);
    if(root.right!=null) // 累加右子树节点个数
        res+=count(root.right);
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.

Memory Usage: 39.4 MB, less than 11.93% of Java online submissions for Kth Smallest Element in a BST.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-230-kth-smallest-element-in-a-bst-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。