二叉搜索树的特点是任意一个节点的值都大于左子树中任意一个节点的值。小于右子树中的任何节点。由于二叉搜索树的特性，我们可以更有效地应用该算法。精读，还记得《算法 - 二叉树》提到的二叉树最近岳父问题吗？如果这是一个二叉搜索树，有没有更聪明的解决方案？你可以停下来想一想。二叉搜索树的最近共同祖先二叉搜索树的最近共同祖先是一个简单的问题。题目如下：给定一棵二叉搜索树，找到树中两个指定节点的最近共同祖先。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x，满足x是p和q的祖先，深度为x尽可能大（一个节点也可以是它自己的祖先）。”第一个判断条件相同，即当前节点值等于p或q，则当前节点为其最近的共同祖先。如果不是呢？同时考虑二叉搜索树和共同祖先的特点，可以发现，如果两个节点p和q分别位于当前节点的左侧或右侧，则当前节点满足要求。如果pq值其中一个大于，另一个小于当前节点，则说明pq分布在当前节点的左右两侧。基于以上考虑，可以只通过值的大小来判断，所以题目就简化了。接下来我们来看一个入门题，即如何验证一棵二叉树是一棵二叉查找树。验证二叉搜索树验证二叉搜索树是一个中级问题。题目如下：给定一棵二叉树，判断它是否是一棵有效的二叉搜索树。假设一棵二叉搜索树具有以下特点：节点的左子树只包含小于当前节点的数字。节点的右子树仅包含大于当前节点的数字。所有的左子树和右子树本身必须是二叉搜索树。这个问题似乎是用非常优雅的递归来实现的。二叉搜索树最重要的是对节点值的限制。如果我们能正确地持有每个节点的值，我们就可以判断。如何判断节点值是否正确？我们可以用递归的方式回推，即从根节点开始，假设根节点的值为x，那么左树节点的值一定小于x，再向左，取值必须小于（假设第一个左节点的值为x1）x1，右树也用同样的方法判断，所以答案可以写成：functionisValidBST(node:TreeNode,min=-Infinity,max=Infinity){if(node===null)returntrue//判断取值范围是否合理？if(node.valmax)returnfalse//继续递归，根据二叉搜索树的特殊性，进一步缩小最大值和最小值的锁定范围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个节点，假设我把第三个节点作为根节点，那么左子树有2个节点，右子树有7个节点。在这个组合中，有DP(2)*DP(7)这么多，假设DP(n)代表了n个结点可以组成任意一棵二叉搜索树的个数。这只是第三个节点是根节点的情况。其实作为根节点的每个节点都是一棵不同的树（轴对称也是不同的），那么我们就要从第一个节点计算到第n个节点。那么答案就出来了，我们考虑特殊情况DP(0)=1DP(1)=1，所以：functionnumTrees(n:number){constdp:number[]=[1,1]for(leti=2;i<=n;i++){for(letj=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j]}}returndp[n]}最后，我们来看一个价值发现问题。不是求最大值，而是求第k大的值。二叉搜索树的第K大节点二叉搜索树的第K大节点是一个简单的问题，题目如下：给定一棵二叉搜索树，请找到第k大节点。这道题之所以简单，是因为二叉查找树的中序遍历是从小到大的，所以只要将中序遍历反过来，就可以找到第k大的结点。逆序遍历，即右、根、左。这个问题就解决了。总结二叉查找树的特点很简单，就是根节点的值夹在左右子树之间，利用这个特点几乎可以解决所有相关问题。但是，通过上面的例子可以发现，仅仅熟悉二叉搜索树的特性是不够的。有些问题需要结合二叉树中序遍历、共祖特性等通用算法思想来解决，因此学会掌握它们非常重要。讨论地址为：精读《算法 - 二叉搜索树》·第337期·dt-fe/weekly想参与讨论的请戳这里，每周都有新话题，周末或周一发布。前端精读——帮你过滤靠谱的内容。关注前端精读微信公众号版权声明：免费转载-非商业-非衍生保留属性（CreativeCommons3.0License）
