LeetCode题目（Python实现）：不同的二叉搜索树 II

末蓝、 2023-07-15 07:59 10阅读 0赞

### 文章目录 ###

*  题目
 *   *  递归
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  动态规划
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

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

**示例**：

输入: 3
    输出:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    解释:
    以上的输出对应以下 5 种不同结构的二叉搜索树：
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

## 递归 ##

### 算法实现 ###

def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        # 如果 为空树
        if not n:
            return []
    
        def new_trees(start, end):
            if start > end:
                return [None]
    
            all_trees = []
            # 针对(start,end)中的每一个i进行切分，也就是求G(i),判断左右是否有节点，通过start和end比较
            for i in range(start, end + 1):
                # 左子树
                left_trees = new_trees(start, i - 1)
                # 右子树
                right_trees = new_trees(i + 1, end)
    
                for left in left_trees:
                    for right in right_trees:
                        tree = TreeNode(i)
                        tree.left = left
                        tree.right = right
                        all_trees.append(tree)
            # print(all_trees)
            # 注：每次递归进入的子树的all_trees都是不一样的。可以通过打印print()查看控制台的输出，这样更容易理解具体的思路。
            return all_trees
    
        return new_trees(1, n)

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 52 ms, 在所有 Python3 提交中击败了87.26%的用户  
**内存消耗** : 15 MB, 在所有 Python3 提交中击败了8.17%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

![在这里插入图片描述][20200315230641512.png]

## 动态规划 ##

### 算法实现 ###

def generateTrees(self, n: int):
    	if n == 0:
    	    return []
    	# 对dp进行初始化
    	dp = []
    	for i in range(0, n + 1):  # 初始化dp
    	    dp.append([])
    	    for j in range(0, n + 1):
    	        if i == j:
    	            dp[i].append([TreeNode(i)])
    	        elif i < j:
    	            dp[i].append([])
    	        else:
    	            dp[i].append([None])
    	dp[0][0] = [None]
    	for i in range(n - 1, 0, -1):  # 自下向上进行循环
    	    for j in range(i + 1, n + 1):
    	        for r in range(i, j + 1):  # i-j每一个节点为顶点的情况
    	            left = r + 1 if r < j else r  # 右边的值需要边界判断，不然会溢出数组
    	            for x in dp[i][r - 1]:  # 左右子树排列组合
    	                for y in dp[left][j]:
    	                    node = TreeNode(r)
    	                    node.left = x
    	                    node.right = y
    	                    if r == j:
    	                        node.right = None
    	                    dp[i][j].append(node)  # dp[i][j]添加此次循环的值
    	return dp[1][n]

### 执行结果 ###

![在这里插入图片描述][202003160010522.png]

## 小结 ##

这次题目想了半天没有思路，看了题解后对递归大致理解了，但是对动态规划也大致明白了，动态规划有点难理解，但说实话画个矩形稍微验算验算就大致明白了该如何运作，看来动态规划得动手，不能光想。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/df0e02022b984831b4d2d441cd9ffef5.png
[20200315230641512.png]: /images/20230528/8e1a686cade6433fa195d873118d1f94.png
[202003160010522.png]: /images/20230528/baec14fdd20e43f8b9680f9a84170589.png