精读

 

还记得 《算法 - 二叉树》 提到的 二叉树的最近公公祖先 问题吗？如果这是一颗二叉搜索树，是不是存在更巧妙的解法？你可以暂停先思考一下。

 

二叉搜索树的最近公共祖先

 

二叉搜索树的最近公共祖先是一道简单题，题目如下：

 

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

 

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

 

第一个判断条件是相同的，即当前节点值等于 p 或 q 任意一个，则当前节点就是其最近公共祖先。

 

如果不是呢？同时考虑二叉搜索树与公共祖先的特性可以发现：

 

如果 pq 两个节点分别位于当前节点的左 or 右边，则当前节点符合要求。

 

如果 pq 值一个大于，一个小于当前节点，说明 pq 分布在当前节点左右两侧。

 

基于以上考虑，可以仅通过值大小来判断，因此题目就被简化了。

 

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

 

验证二叉搜索树

 

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

 

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

 

假设一个二叉搜索树具有如下特征：

 

节点的左子树只包含小于当前节点的数。

 

节点的右子树只包含大于当前节点的数。

 

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

 

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

 

二叉搜索树最重要的就是对节点值的限制，我们如果能正确卡住每个节点的值，就可以判断了。

 

如何判断节点值是否正确呢？我们可以用递归的方式倒推，即从根节点开始，假设根节点值为 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) 显然不能重新构造，我们需要仔细考虑。

 

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

 

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

 

可以看到，删除二叉搜索树，为了让二叉搜索树性质保持不变，需要不断进行重复子问题的递归删除节点。

 

当你掌握二叉搜索树特性后，可以尝试构造二叉搜索树了，下面就是一道让你任意构造二叉搜索树的题目：不同的二叉搜索树。