二叉搜索树相关题目总结（二） 力扣 Python

前文 二叉搜索树相关题目总结（一） 中，主要是涉及二叉搜索树中的一些操作。

这篇文章是列举两道与构造 BST 有关的题目。

96. 不同的二叉搜索树

解题思路：

给定一个 n， 问从 1 到 n 能组成互不相同的 BST 有几种？

简单来看，就是穷举所有可能的树，然后算一下结果。

第一种方法，递归 DFS, 也是回溯的一种体现。

加入了名为 cache 的数组，也就是 dp 数组用于消除子问题重叠。

class Solution:
    
    def numTrees(self, n: int) -> int:
        cache = [-1] * (n + 1) # 初始化数组长度
        return self.countTrees(n, cache)

    def countTrees(self,n, cache):
    	#两个 base case
        if n == 0: 
            return 1
        if n == 1:
            return 1
		
		# -1 是数组初始化的值，只要不是 -1 就是已经存在的子问题，直接返回
        if cache[n] != -1: 
            return cache[n]
		#记录总的个数
        res = 0
        for i in range(n):
        	#分别列举可能构成的左右子树个数
            LeftTrees = self.countTrees(i, cache)
            RightTrees = self.countTrees(n - i - 1, cache)
			#以 i 为节点的树，其能构成不同的 BST 数目为 左右子树的乘机
            res += LeftTrees * RightTrees
        #从下往上记录节点组成树的个数
        cache[n] = res
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

解法二：

其实和解法一一致，只不过引入了 lru_cache 包，可以理解为一个隐式 cache 装饰器，用于自动缓存子问题。

代码相对于简洁。

class Solution:
    def numTrees(self, n: int) -> int:
        return self.countTrees(n)
    
    @lru_cache
    def countTrees(self, n: int) -> int:
        if n == 0:
            return 1

        if n == 1:
            return 1
 
        res = 0
        for i in range(n):
            left = self.countTrees(i)
            right = self.countTrees(n - i - 1)
            res += left * right

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法三：

动态规划，动态规划不明白可以看一下官方解释的图。

动态规划是一种从底向上的 DFS。

dp 数组用于记录重复子问题。

class Solution:
	def numTrees(self, n: int) -> int:
		#初始化 dp 数组
		dp = [0] * (n + 1)
    	dp[0], dp[1] = 1, 1

    	for i in range(2, n + 1):
       		for j in range(i):
        		#动态转移方程，穷举子问题
            	dp[i] += dp[j] * dp[i - j - 1]
        
     	return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12

95. 不同的二叉搜索树 II

解题思路：
与 一思路一致，但这次要具体列出可能的子树，直接使用 DFS 然后记录每次可能的子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:

        if n == 0:
            return []

        return self.helper(1, n)

    def helper(self, start, end):

        if start > end:
            return[None]

        #记录所有可能的二叉搜索树
        res = []

        #对每一个数值穷举
        for curRoot in range(start , end + 1):

            #递归生成可能的左右子树
            leftSubtrees = self.helper(start, curRoot - 1)
            rightSubtrees = self.helper(curRoot + 1, end)

            for leftTree in leftSubtrees:
                for rightTree in rightSubtrees:

                    #合并每一个可能的组合
                    root = TreeNode(curRoot)
                    root.left = leftTree
                    root.right = rightTree
                    #添加组合
                    res.append(root)
                    
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40