LeetCode--230.二叉搜索树中第K小的元素(JavaScript)

给定一个二叉搜索树,编写一个函数 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-1 个元素即可。

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
/** * @param {TreeNode} root * @param {number} k * @return {number} */
var kthSmallest = function(root, k) {
  let res = []
  const inorder = (root) => {
    if (root) {
      inorder(root.left);
      res.push(root.val);
      inorder(root.right);
    }
  }
  inorder(root);
  return res[k-1]
};

进阶版:

采用递归的方法,先求出根节点左子树的所有节点数 leftNum,

  const count = (root) => {
    if (!root) {
      return 0;
    } else {
      return 1 + count(root.left) + count(root.right);
    }
  }
  1. leftNum < k - 1 , 说明第 k 个元素在根节点的右子树中,递归返回 kthSmallest(root.right, k - leftNum - 1)
  2. leftNum = k - 1,说明第 k 个元素刚好是根节点,返回根节点的值即可
  3. leftNum > k - 1,说明第 k 个元素在根节点的左子树中,递归返回kthSmallest(root.left, k)

使用递归的好处是不用额外空间,并且当树频繁修改时,也可以很好的适应。
全部代码:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
/** * @param {TreeNode} root * @param {number} k * @return {number} */
var kthSmallest = function(root, k) {
  const count = (root) => {
    if (!root) {
      return 0;
    } else {
      return 1 + count(root.left) + count(root.right);
    }
  }
  
  let leftNum = count(root.left);
  if (leftNum === k - 1) {
    return root.val;
  } else if (leftNum > k - 1) {
    return kthSmallest(root.left, k)
  } else {
    return kthSmallest(root.right, k - leftNum - 1)
  }
};
全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
你找工作的时候用AI吗?
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务