数据结构进阶篇，二叉搜索树专题

作者：小桥流水78 | 2024-07-27 23:33:32

踩

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k

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

「题目：」

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

「示例：」

输入：root = [3,1,4,null,2], k = 1 ，输出：1。

「解题思路：」

由于这是一个二叉搜索树，所以其中序序列是一个严格的递增序列。

那么本道题就转化为寻找中序序列中第 k 个元素的问题。

时间复杂度：O(n)，空间复杂度：O(n)。


const kthSmallest = (root, k) => {
  let ans = 0;
  let count = 0;
 
  const dfs = (root) => {
    if (!root) {
      return;
    }
    dfs(root.left);
    if (++count === k) {
      ans = root.val;
      return;
    }
    dfs(root.right);
  }
 
  dfs(root);
 
  return ans;
}

450. 删除二叉搜索树中的节点

「题目：」

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

「示例：」

root = [5,3,6,2,4,null,7], key = 3，输出：[5,4,6,2,null,null,7]。

「解题思路：」

首先，通过递归遍历可以很容易地找到目标节点，然后需要处理三种情况：

当前节点值大于目标值。
当前节点值小于目标值。
当前节点值等于目标值。

针对第一种情况：利用二叉搜索树中左子树的所有节点严格小于根节点的特性，那么目标值必定存在于当前根节点的左子树中，对其左子树进行删除操作即可。

同理，针对第二种情况，对其右子树进行删除操作。

第三种情况比较复杂，又分为以下两种情况：

存在一个或者零个子树。
左右子树都存在。

针对第一种情况：只需要返回对应的子树即可。

针对第二种情况：需要在删除目标元素之后，仍然保持二叉搜索树的特性，所以需要在其右子树中找出最小的元素，作为新的根节点。

这里采用值替换的方式，然后再对右子树进行最小值的删除操作。

时间复杂度：O(logn)，空间复杂度：O(n)。


const deleteNode = (root, key) => {
  if (!root) {
    return null;
  }
 
  const rootVal = root.val;
  if (rootVal > key) {
    root.left = deleteNode(root.left, key);
  } else if (rootVal < key) {
    root.right = deleteNode(root.right, key);
  } else {
    if (root.left && root.right) {
      let min = root.right;
      while (min.left) {
        min = min.left;
      }
      root.val = min.val;
      root.right = deleteNode(root.right, min.val);
    } else {
      return root.left ? root.left : root.right;
    }
  }
 
  return root;
}

701. 二叉搜索树中的插入操作

「题目：」

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

「示例：」

输入：root = [4,2,7,1,3], val = 5，输出：[4,2,7,1,3,5]。

「解题思路：」

本道题仍然是利用二叉搜索树的特性：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值。

在递归遍历的过程中，不断比较当前根节点与目标值的大小，从而转化为将目标值插入到左子树或者右子树的问题。

当当前根节点为空时，就是目标值插入的位置，并且需要链接到其父节点上。

时间复杂度：O(height)，空间复杂度：O(1)。


const insertIntoBST = (root, val) => {
  if (!root) {
    return new TreeNode(val);
  }
 
  if (root.val > val) {
    root.left = insertIntoBST(root.left, val);
  }
 
  if (root.val < val) {
    root.right = insertIntoBST(root.right, val);
  }
 
  return root;
}

写在最后

LeetCode 数据结构篇根据难度划分为：

数据结构入门篇
数据结构进阶篇
数据结构高级进阶篇

每篇会根据题目的类型和解题思路形成不同的专题，这样更利于摸清本质，将技巧内化于心。

感兴趣的小伙伴可以关注下方的公众号，或者微信搜索“漫谈大前端”，如果本文对你有帮助，欢迎点赞、分享、转发。