​LeetCode刷题实战95:不同的二叉搜索树 II

程序IT圈

共 4490字,需浏览 9分钟

 ·

2020-11-18 01:46

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 不同的二叉搜索树 II,我们先来看题面:

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

题意


给定一个整数 n,生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

样例


解题

https://www.cnblogs.com/techflow/p/13594735.html

拿到手我们思路没多少,但是发现的问题却一大堆。比如说我们怎么构建这些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时的所有结果呢?
当然是可以的,实际上这也是一个很好的做法。这是一种最基本的二叉树,假设我们要往其中插入一个最大的节点,我们很容易发现,一共有三种方法。
image-20200809155208137
第一种方法将原搜索树作为新节点的左孩子节点。
第二种方法是将新的节点插入根节点的右侧,代替根节点的右孩子。由于这个新加入的节点大于其他所有节点,所以根节点的右孩子会变成它的左孩子。
最后一种方法就是将它变成叶子节点,也就是放在最底层。
我们稍加思考就可以想明白,如果要把一个最大的元素插入BST,那么它只能够放在最右侧的树分支上。也就是说当我们从n=k的情况推导k+1时,根据最右侧链路长度的不同,会衍生出多个解来。只要抓住了这一点,这其中的递推关系就很明显了。
我们用代码来实现这个想法,思路虽然简单,但是实现起来要复杂一些,有很多细节需要考虑。我在这里不一一列举了,大家查看代码当中的注释吧。

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        ret = []
        
        # 拷贝二叉树
        def copyTree(node):
            if node is None:
                return None
            u = TreeNode(node.val)
            u.left = copyTree(node.left)
            u.right = copyTree(node.right)
            return u
        
        def dfs(n):
            # n=1只有一种情况
            if n == 1:
                ret.append(TreeNode(1))
                return
            
            dfs(n-1)
            # 遍历n=k时的所有情况
            for i in range(len(ret)):
                u = ret[i]
                node = TreeNode(n)
                node.left = u
                ret[i] = node
                
                it = u
                rank = 0
                # 将n插入最右侧链路当中,有几种可以选择的位置,就会诞生几种新的放法
                while it is not None:
                    node = TreeNode(n)
                    # 为了防止答案之间互不影响,所以需要把树拷贝一份
                    new = copyTree(u)
                    cur = new
                    
                    # rank记录的是每一个解对应的n放入的深度
                    for _ in range(rank):
                        cur = cur.right
                    
                    node.left = cur.right
                    cur.right = node
                    
                    ret.append(new)
                    
                    it = it.right
                    rank += 1
            
        if n == 0:
            return ret
        dfs(n)
        return ret


这种方法当然是可行的, 我们也成功做了出来。但是它也有很多问题,最大的问题就是细节太多,而且处理起来太麻烦了。那么有没有简单一点的方法呢?
我们来思考一个问题,我们通过递推和迭代从n=k构造出了n=k+1的情况,这一种构造和递推的思路非常巧妙。但问题是,我们构造和递推的方法难道只有这一种吗?能不能想出其他简便一些的构造和递推的方法呢?
既然我这么说,那么很显然,它是可以的,怎么做呢?
这要用到BST另外一个性质,我们都知道对于BST来说,它有一个性质是对于根节点来说,所有比它小的元素都出现在它的左侧,比它大的元素都在它的右侧。那么假如我们知道根节点是i,那么我们可以确定1到i-1出现在它的左子树,i+1到n出现在它的右子树。假设说我们已经得到了左右子树的所有情况,我们只需要把它们两两组合在一起,是不是就得到了答案了呢?
我这么说你们理解起来可能还是会觉得有些费劲,但是一旦查看代码,你们一定会为这段逻辑的简易性而折服,看起来实在是太简明也太巧妙了。

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        ret = []
        
        def dfs(l, r):
            cur = []
            if r < l:
                cur.append(None)
                return cur
            
            # 枚举作为树根的元素
            for i in range(l, r+1):
                # 枚举左右子树的所有子树的构成情况
                for u in dfs(l, i-1):
                    for v in dfs(i+1, r):
                        node = TreeNode(i)
                        node.left = u
                        node.right = v
                        cur.append(node)
            return cur
            
        if n == 0:
            return ret
        return dfs(1, n)


和上面的方法一样,这也是递归和构造方法的结合,但显然无论从运行效率上还是代码的简易性上,这种做法都要好不少,实实在在地体现了代码和逻辑之美。
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:

LeetCode50-80题汇总,速度收藏!
LeetCode刷题实战81:搜索旋转排序数组 II
LeetCode刷题实战82:删除排序链表中的重复元素 II
LeetCode刷题实战83:删除排序链表中的重复元素
LeetCode刷题实战84: 柱状图中最大的矩形
LeetCode刷题实战85:最大矩形
LeetCode刷题实战86:分隔链表
LeetCode刷题实战87:扰乱字符串
LeetCode刷题实战88:合并两个有序数组
LeetCode刷题实战89:格雷编码
LeetCode刷题实战90:子集 II
LeetCode刷题实战91:解码方法
LeetCode刷题实战92:反转链表 II
LeetCode刷题实战93:复原IP地址
LeetCode刷题实战94:二叉树的中序遍历

浏览 41
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报