【LeetCode】动态规划—95. 不同的二叉搜索树 II（附完整Python/C++代码）

题目描述

前言

不同的二叉搜索树 II 是一个要求构造出所有可能的 二叉搜索树（BST） 的问题。给定一个整数 n，我们需要构造出由 1 到 n 为节点的所有不同形态的二叉搜索树，并返回这些树的根节点列表。该问题与 不同的二叉搜索树 I 不同的是，不仅要求计算不同二叉搜索树的数量，还需要输出所有可能的二叉搜索树的具体结构。

---

基本思路

1. 问题定义

给定一个整数 n，构造所有包含 1 到 n 的不同二叉搜索树，并返回这些树的根节点列表。每个二叉搜索树的节点只能使用一次，且必须保持 二叉搜索树 的性质。

二叉搜索树的性质：

• 左子树的所有节点值都小于根节点值。
• 右子树的所有节点值都大于根节点值。

2. 理解问题和递推关系

递归构造思想：

我们可以使用递归的方法来构造二叉搜索树。对于任意一个 i，它可以作为根节点，1 到 i-1 组成它的左子树，i+1 到 n 组成它的右子树。递归构造左子树和右子树，并将不同的子树组合起来。

状态定义：

1. 对于区间 [start, end]，构造由该区间组成的所有二叉搜索树。
2. 递归地将每个数字作为根节点，左子树由 [start, i-1] 构造，右子树由 [i+1, end] 构造。
3. 组合所有左子树和右子树，形成不同的二叉搜索树。

递推公式：

1. 对于每个根节点 i，构造左子树 generateTrees(start, i-1) 和右子树 generateTrees(i+1, end)。
2. 将左右子树的所有组合与根节点 i 连接，形成不同的树形结构。

终止条件：

• 当 start > end 时，返回 None，表示当前区间不能构成任何子树。

3. 解决方法

递归 + 动态规划方法：

1. 定义递归函数 generateTrees(start, end) 来构造 [start, end] 范围内的所有二叉搜索树。
2. 对于每一个 i 作为根节点，递归构造左子树和右子树，并将其组合。
3. 最终返回所有构造的树。

伪代码：

function generateTrees(start, end):if start > end:return [None]all_trees = []for i from start to end:# 构造左子树和右子树left_trees = generateTrees(start, i-1)right_trees = generateTrees(i+1, end)# 组合左右子树与根节点for each left in left_trees:for each right in right_trees:root = new TreeNode(i)root.left = leftroot.right = rightall_trees.append(root)return all_trees

特别注意：

• 递归调用会确保每个节点 i 都尝试作为根节点，并且分别生成左右子树。最终所有树形结构都被记录在结果列表中。

4. 进一步优化

• 缓存递归结果：可以用备忘录的方式存储已经计算过的子树组合，避免重复计算，进一步优化效率。

5. 小总结

• 问题思路：利用递归和分治的思想构造出所有二叉搜索树的结构，确保每个节点都作为一次根节点，并递归构造左右子树。
• 时间复杂度：时间复杂度较高，因每次递归会构造不同的树形结构，复杂度为 超指数级别。

以上就是不同的二叉搜索树 II问题的基本思路。

---

Python代码

# 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 []# 递归函数，生成从start到end的所有二叉搜索树def generateTrees(start, end):if start > end:return [None]  # 返回一个空树all_trees = []  # 存储所有可能的二叉搜索树for i in range(start, end + 1):# 构造左子树和右子树left_trees = generateTrees(start, i - 1)right_trees = generateTrees(i + 1, end)# 组合所有的左子树和右子树for left in left_trees:for right in right_trees:root = TreeNode(i)  # 以i作为根节点root.left = leftroot.right = rightall_trees.append(root)return all_treesreturn generateTrees(1, n)

Python代码解释

1. 定义递归函数：generateTrees(start, end) 用于生成从 start 到 end 所有不同的二叉搜索树。
2. 递归构造：对于每个 i 作为根节点，递归构造左右子树的所有可能组合。
3. 返回结果：最终返回所有可能的树形结构的根节点列表。

---

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> generateTrees(int n) {if (n == 0) return {};// 递归函数，生成从start到end的所有二叉搜索树return generateTrees(1, n);}vector<TreeNode*> generateTrees(int start, int end) {if (start > end) return {nullptr};  // 返回一个空树vector<TreeNode*> all_trees;  // 存储所有可能的二叉搜索树for (int i = start; i <= end; ++i) {// 构造左子树和右子树vector<TreeNode*> left_trees = generateTrees(start, i - 1);vector<TreeNode*> right_trees = generateTrees(i + 1, end);// 组合所有的左子树和右子树for (TreeNode* left : left_trees) {for (TreeNode* right : right_trees) {TreeNode* root = new TreeNode(i);  // 以i作为根节点root->left = left;root->right = right;all_trees.push_back(root);}}}return all_trees;}
};

C++代码解释

1. 定义递归函数：generateTrees(start, end) 用于生成从 start 到 end 所有不同的二叉搜索树。
2. 递归构造：对于每个 i 作为根节点，递归构造左右子树的所有可能组合。
3. 返回结果：最终返回所有可能的树形结构的根节点列表。

---

总结

• 核心思想：通过递归和分治的思想，将问题分解为左右子树的组合问题。每个节点都可以作为根节点，递归构造其左子树和右子树，再组合这些树形结构。
• 复杂度分析：由于需要构造所有可能的树，时间复杂度较高，是 超指数级别 的问题。这类问题适合使用动态规划或递归解决，但无法避免高复杂度。
• 递归的应用：本问题是递归和分治思想的典型应用，尤其适合解决树形结构的构造问题。