关于javascript:精读算法-二叉搜索树

二叉搜寻树的个性是，任何一个节点的值：

都大于左子树任意节点。
都小于右子树任意节点。

因为二叉搜寻树的个性，咱们能够更高效的利用算法。

还记得《算法 – 二叉树》提到的二叉树的最近公公先人问题吗？如果这是一颗二叉搜寻树，是不是存在更奇妙的解法？你能够暂停先思考一下。

二叉搜寻树的最近公共先人是一道简略题，题目如下：

给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。

百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”

第一个判断条件是雷同的，即以后节点值等于 p 或 q 任意一个，则以后节点就是其最近公共先人。

如果不是呢？同时思考二叉搜寻树与公共先人的个性能够发现：

如果 p q 两个节点别离位于以后节点的左 or 左边，则以后节点符合要求。
如果 p q 值一个大于，一个小于以后节点，阐明 p q 散布在以后节点左右两侧。

基于以上思考，能够仅通过值大小来判断，因而题目就被简化了。

接下来看一道入门题，即如何验证一颗二叉树是二叉搜寻树。

验证二叉搜寻树是一道中等题，题目如下：

给定一个二叉树，判断其是否是一个无效的二叉搜寻树。

假如一个二叉搜寻树具备如下特色：

节点的左子树只蕴含小于以后节点的数。

节点的右子树只蕴含大于以后节点的数。

所有左子树和右子树本身必须也是二叉搜寻树。

这道题看上去就应该用十分优雅的递归来实现。

二叉搜寻树最重要的就是对节点值的限度，咱们如果能正确卡住每个节点的值，就能够判断了。

如何判断节点值是否正确呢？咱们能够用递归的形式倒推，即从根节点开始，假如根节点值为 x，那么左树节点的值就必须小于 x，再往左，那么值就要小于（假如第一个左节点值为 x1）x1，右树也是一样判断，因而就能够写出答案：

function isValidBST(node: TreeNode, min = -Infinity, max = Infinity) {if (node === null) return true
  // 判断值范畴是否正当
  if (node.val < min || node.val > max) return false
  // 持续递归，并且依据二叉搜寻树特定，进一步放大最大、最小值的锁定范畴
  return 
    // 左子树值 max 为以后节点值
    isValidBST(node.left, min, node.val) &&
    // 右子树值 min 为以后节点值
    isValidBST(node.right, node.val, max) &&
}

接下来看一些简略的二叉搜寻树操作问题，比方删除二叉搜寻树中的节点。

删除二叉搜寻树中的节点是一道中等题，题目如下：

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

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

首先找到须要删除的节点；

如果找到了，删除它。

阐明：要求算法工夫复杂度为 O(h)，h 为树的高度。

要删除二叉搜寻树的节点，找到节点自身并不难，因为如果值小了，就从左子树找；如果值大了，就从右子树找，这自身查找起来是非常简单的。难点在于，如何保障删除元素后，这棵树还是一颗二叉搜寻树？

假如咱们删除的是叶子结点，很显然，二叉搜寻树任意子树都是二叉搜寻树，咱们又没有毁坏其余节点的关系，因而间接删除就行了，最简略。

如果删除的不是叶子结点，那么谁来“上位”代替这个节点呢？题目要求复杂度为 O(h) 显然不能从新结构，咱们须要认真思考。

假如删除的节点存在右节点，那么必定从右节点找到一个代替值移上来，找谁呢？找右节点的最小值呀，最小值很好找的，找完代替后，相当于 问题转移为删除这个最小值节点，递归就完事了。

假如删除的节点存在左节点，然而没有右节点，那就从左节点找一个最大的替换掉，同理递归删除找到的节点。

能够看到，删除二叉搜寻树，为了让二叉搜寻树性质放弃不变，须要一直进行重复子问题的递归删除节点。

当你把握二叉搜寻树个性后，能够尝试结构二叉搜寻树了，上面就是一道让你任意结构二叉搜寻树的题目：不同的二叉搜寻树。

不同的二叉搜寻树是一道中等题，题目如下：

给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不雷同的 二叉搜寻树 有多少种？返回满足题意的二叉搜寻树的种数。

这道题重点在于动静布局思维 + 笛卡尔积组合的思维。

须要将所有可能性设想为确定了根节点后，左右子树到底有几种组合形式？

举个例子，假如 n=10，那么这 10 个节点，假如我取第 3 个节点为根节点，那么左子树有 2 个节点，右子树有 7 个节点，这种组合状况就有 DP(2) * DP(7) 这么多，假如 DP(n) 示意 n 个节点能组成任意二叉搜寻树的数量。

这仅是第 3 个节点为根节点的状况，实际上每个节点作为根节点都是不同的树（轴对称也算不同的），那么咱们就要从第 1 个节点计算到第 n 个节点。

因而答案就进去了，咱们先思考非凡状况 DP(0)=1 DP(1)=1，所以：

function numTrees(n: number) {const dp: number[] = [1, 1]

  for (let i = 2; i <= n; i++) {for (let j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j]
    }
  }

  return dp[n]
}

最初再看一道找值题，并不是找最大值，而是找第 k 大值。

二叉搜寻树的第 K 大节点是一道简略题，题目如下：

给定一棵二叉搜寻树，请找出其中第 k 大的节点。

这道题之所以简略，是因为二叉搜寻树的中序遍历是从小到大的，因而只有倒序中序遍历，就能够找到第 k 大的节点。

倒序中序遍历，即右、根、左。

这道题就解决啦。

二叉搜寻树的个性很简略，就是根节点值夹在左右子树两头，利用这个个性简直能够解决所有相干问题。

但通过下面几个例子能够发现，仅相熟二叉搜寻树个性还是不够的，一些题目须要联合二叉树中序遍历、公共先人特色等通用算法思路联合来解决，因而学会死记硬背很重要。

探讨地址是：精读《算法 – 二叉搜寻树》· Issue #337 · dt-fe/weekly

如果你想参加探讨，请点击这里，每周都有新的主题，周末或周一公布。前端精读 – 帮你筛选靠谱的内容。

关注 前端精读微信公众号

版权申明：自在转载 - 非商用 - 非衍生 - 放弃署名（创意共享 3.0 许可证）

精读

二叉搜寻树的最近公共先人

验证二叉搜寻树

删除二叉搜寻树中的节点

不同的二叉搜寻树

二叉搜寻树的第 K 大节点

总结