203

ascoders · ascoders · commit 9b9d02b9de5d · 2021-07-19T10:07:31.000+08:00
diff --git a/readme.md b/readme.md
@@ -6,7 +6,7 @@
 
 前端界的好文精读，每周更新！
 
-最新精读：<a href="./前沿技术/202.精读《React 18》.md">202.精读《React 18》</a>
+最新精读：<a href="./算法/203.精读《算法 - 二叉搜索树》.md">203.精读《算法 - 二叉搜索树》</a>
 
 素材来源：[周刊参考池](https://github.com/ascoders/weekly/issues/2)
 
@@ -236,6 +236,7 @@
 - <a href="./算法/199.精读《算法 - 滑动窗口》.md">199.精读《算法 - 滑动窗口》</a>
 - <a href="./算法/200.精读《算法 - 回溯》.md">200.精读《算法 - 回溯》</a>
 - <a href="./算法/201.精读《算法 - 二叉树》.md">201.精读《算法 - 二叉树》</a>
+- <a href="./算法/203.精读《算法 - 二叉搜索树》.md">203.精读《算法 - 二叉搜索树》</a>
 
 ## 关注前端精读微信公众号
 
diff --git a/前沿技术/202.精读《React 18》.md b/前沿技术/202.精读《React 18》.md
@@ -111,7 +111,7 @@ const root = ReactDOM.hydrateRoot(container, <App tab="home" />);
 
 - startTransition。
 - useDeferredValue。
-- <SuspenseList>。
+- &lt;SuspenseList&gt;。
 
 后两个文档还未放出，所以本文只介绍第一个 API：startTransition。首先看一下用法：
 
diff --git a/算法/203.精读《算法 - 二叉搜索树》.md b/算法/203.精读《算法 - 二叉搜索树》.md
@@ -0,0 +1,150 @@
+二叉搜索树的特性是，任何一个节点的值：
+
+- 都大于左子树任意节点。
+- 都小于右子树任意节点。
+
+因为二叉搜索树的特性，我们可以更高效的应用算法。
+
+## 精读
+
+还记得 [《算法 - 二叉树》](https://github.com/ascoders/weekly/blob/master/%E7%AE%97%E6%B3%95/201.%E7%B2%BE%E8%AF%BB%E3%80%8A%E7%AE%97%E6%B3%95%20-%20%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%8B.md) 提到的 [二叉树的最近公公祖先](https://github.com/ascoders/weekly/blob/master/%E7%AE%97%E6%B3%95/201.%E7%B2%BE%E8%AF%BB%E3%80%8A%E7%AE%97%E6%B3%95%20-%20%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%8B.md) 问题吗？如果这是一颗二叉搜索树，是不是存在更巧妙的解法？你可以暂停先思考一下。
+
+### 二叉搜索树的最近公共祖先
+
+二叉搜索树的最近公共祖先是一道简单题，题目如下：
+
+> 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
+>
+> 百度百科中最近公共祖先的定义为：“对于有根树 `T` 的两个结点 `p`、`q`，最近公共祖先表示为一个结点 `x`，满足 `x` 是 `p`、`q` 的祖先且 `x` 的深度尽可能大（一个节点也可以是它自己的祖先）。”
+
+第一个判断条件是相同的，即当前节点值等于 `p` 或 `q` 任意一个，则当前节点就是其最近公共祖先。
+
+如果不是呢？同时考虑二叉搜索树与公共祖先的特性可以发现：
+
+1. 如果 `p` `q` 两个节点分别位于当前节点的左 or 右边，则当前节点符合要求。
+2. 如果 `p` `q` 值一个大于，一个小于当前节点，说明 `p` `q` 分布在当前节点左右两侧。
+
+基于以上考虑，可以仅通过值大小来判断，因此题目就被简化了。
+
+接下来看一道入门题，即如何验证一颗二叉树是二叉搜索树。
+
+### 验证二叉搜索树
+
+验证二叉搜索树是一道中等题，题目如下：
+
+> 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
+>
+> 假设一个二叉搜索树具有如下特征：
+>
+> - 节点的左子树只包含小于当前节点的数。
+> - 节点的右子树只包含大于当前节点的数。
+> - 所有左子树和右子树自身必须也是二叉搜索树。
+
+这道题看上去就应该用非常优雅的递归来实现。
+
+二叉搜索树最重要的就是对节点值的限制，我们如果能正确卡住每个节点的值，就可以判断了。
+
+如何判断节点值是否正确呢？我们可以用递归的方式倒推，即从根节点开始，假设根节点值为 `x`，那么左树节点的值就必须小于 `x`，再往左，那么值就要小于（假设第一个左节点值为 `x1`） `x1`，右树也是一样判断，因此就可以写出答案：
+
+```typescript
+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 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
+>
+> 一般来说，删除节点可分为两个步骤：
+>
+> 1. 首先找到需要删除的节点；
+> 2. 如果找到了，删除它。
+>
+> 说明： 要求算法时间复杂度为 `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`，所以：
+
+```typescript
+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` 大的节点。
+
+这道题之所以简单，是因为二叉搜索树的中序遍历是从小到大的，因此只要倒序中序遍历，就可以找到第 `k` 大的节点。
+
+倒序中序遍历，即右、根、左。
+
+这道题就解决啦。
+
+## 总结
+
+二叉搜索树的特性很简单，就是根节点值夹在左右子树中间，利用这个特性几乎可以解决一切相关问题。
+
+但通过上面几个例子可以发现，仅熟悉二叉搜索树特性还是不够的，一些题目需要结合二叉树中序遍历、公共祖先特征等通用算法思路结合来解决，因此学会融会贯通很重要。
+
+> 讨论地址是：[精读《算法 - 二叉搜索树》· Issue #337 · dt-fe/weekly](https://github.com/dt-fe/weekly/issues/337)
+
+**如果你想参与讨论，请 [点击这里](https://github.com/dt-fe/weekly)，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。**
+
+> 关注 **前端精读微信公众号**
+
+<img width=200 src="https://img.alicdn.com/tfs/TB165W0MCzqK1RjSZFLXXcn2XXa-258-258.jpg">
+
+> 版权声明：自由转载-非商用-非衍生-保持署名（[创意共享 3.0 许可证](https://creativecommons.org/licenses/by-nc-nd/3.0/deed.zh)）
