LeetCode 95 | 构造出所有二叉搜索树 今天是LeetCode专题第61篇文章，我们一起来看的是LeetCode95题，Unique Binary Search Trees II（不同的二叉搜索树II）。 这道题的官方难度是Medium，点赞2298，反对160，通过率40.5%。我也仿照steam当中游戏评论的分级，给LeetCode中的题目也给出一个评级标准。按照这个点赞和反对的比例，这道题可以评到特别好评。从题目内容上来说，这是一道不可多得基础拷问的算法题，看着不简单，做起来也不简单，但看了题解之后，你会发现也没你想象得那么难。 题意 给定一个n，表示1到n这n个数字，要求用这n个数构建二叉搜索树（Binary Search Tree）简称BST，要求我们构建出所有不同的二叉搜索树。 样例 从这个case当中我们可以看到，当n=3的时候，二叉搜索树一共有5中不同的情况。为了方便展示，Output当中展示的内容是这些树中序遍历的结果。但实际上我们要返回的是树根节点构成的list。 哦哦，对了题目当中还有一个n <= 8的条件，所以如果你是一个狼人的话，也可以把所有的情况都手动实现。 解法 这道题我感觉官方难得给的有点低了，应该可以算得上是Hard了。拿到手我们思路没多少，但是发现的问题却一大堆。比如说我们怎么构建这些BST，并且怎么判断两颗BST是否重复呢？难道要整个遍历一遍之后，一个节点一个节点地判断是否相同吗？显然这也太耗时了，而且编码也不容易。举个例子[2, 1, 3]和[2, 3, 1]生成的BST是一样的，这种情况很难解决。 即使我们解决了这个问题，那么又怎么样保证我们可以顺利找到所有的答案，而不会有所遗漏呢？这两个核心的问题很难回答，并且你会发现越想越复杂。 这个有点像什么呢？就好像是古代行军打仗，攻打一个异常坚固的堡垒，正面攻坚可能非常困难，我们想出来的办法都在敌人的预料之中，总能找到激活成功教程之道。这个时候就需要我们有敏锐的意识，就好像是一个经验丰富的老将，观察地形之后发现强攻不可为，那么自然就会退下来想一想其他的办法。 我们做题也是一样，正面硬刚做不出来，再耗下去也不会有好办法，往往就需要出奇制胜了。 我们试着把问题缩小，化整为零，如果n=1，那么很简单，BST就只有一种，这个是我们都知道的东西。如果n=2呢，也不难，只有两种，无非是[1, 2]和[2, 1]。这时候我们停住，来思考一个问题，n=2的情况和n=1的情况有什么区别呢？ 如果仔细想，会发现其实没什么区别， 我们只不过是在n=1的情况当中加入了2这个数字而已。同理，我们发散一下n=k和n=k+1的时候生成的BST之间有什么关系呢？如果我们知道了n=k时候的所有BST，可不可以利用这个关系生成n=k+1时的所有结果呢？ 当然是可以的，实际上这也是一个很好的做法。这是一种最基本的二叉树，假设我们要往其中插入一个最大的节点，我们很容易发现，一共有三种方法。
第一种方法将原搜索树作为新节点的左孩子节点。
第二种方法是将新的节点插入根节点的右侧，代替根节点的右孩子。由于这个新加入的节点大于其他所有节点，所以根节点的右孩子会变成它的左孩子。
最后一种方法就是将它变成叶子节点，也就是放在最底层。
我们稍加思考就可以想明白，如果要把一个最大的素插入BST，那么它只能够放在最右侧的树分支上。也就是说当我们从n=k的情况推导k+1时，根据最右侧链路长度的不同，会衍生出多个解来。只要抓住了这一点，这其中的递推关系就很明显了。 我们用代码来实现这个想法，思路虽然简单，但是实现起来要复杂一些，有很多细节需要考虑。我在这里不一一列举了，大家查看代码当中的注释吧。 这种方法当然是可行的， 我们也成功做了出来。但是它也有很多问题，最大的问题就是细节太多，而且处理起来太麻烦了。那么有没有简单一点的方法呢？ 我们来思考一个问题，我们通过递推和迭代从n=k构造出了n=k+1的情况，这一种构造和递推的思路非常巧妙。但问题是，我们构造和递推的方法难道只有这一种吗？能不能想出其他简便一些的构造和递推的方法呢？ 既然我这么说，那么很显然，它是可以的，怎么做呢？ 这要用到BST另外一个性质，我们都知道对于BST来说，它有一个性质是对于根节点来说，所有比它小的素都出现在它的左侧，比它大的素都在它的右侧。那么假如我们知道根节点是i，那么我们可以确定1到i-1出现在它的左子树，i+1到n出现在它的右子树。假设说我们已经得到了左右子树的所有情况，我们只需要把它们两两组合在一起，是不是就得到了答案了呢？ 我这么说你们理解起来可能还是会觉得有些费劲，但是一旦查看代码，你们一定会为这段逻辑的简易性而折服，看起来实在是太简明也太巧妙了。 和上面的方法一样，这也是递归和构造方法的结合，但显然无论从运行效率上还是代码的简易性上，这种做法都要好不少，实实在在地体现了代码和逻辑之美。 今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（、转发、点赞）。 - END – 原文链接：LeetCode 95 | 构造出所有二叉搜索树
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/71219.html
