【LeetCode】动态规划—95. 不同的二叉搜索树 II（附完整Python/C++代码）
动态规划—95. 不同的二叉搜索树 II
题目描述
前言
不同的二叉搜索树 II 是一个要求构造出所有可能的 二叉搜索树（BST） 的问题。给定一个整数 n，我们需要构造出由 1 到 n 为节点的所有不同形态的二叉搜索树，并返回这些树的根节点列表。该问题与 不同的二叉搜索树 I 不同的是，不仅要求计算不同二叉搜索树的数量，还需要输出所有可能的二叉搜索树的具体结构。
基本思路
1. 问题定义
给定一个整数 n，构造所有包含 1 到 n 的不同二叉搜索树，并返回这些树的根节点列表。每个二叉搜索树的节点只能使用一次，且必须保持 二叉搜索树 的性质。
二叉搜索树的性质：
- 左子树的所有节点值都小于根节点值。
- 右子树的所有节点值都大于根节点值。
2. 理解问题和递推关系
递归构造思想：
我们可以使用递归的方法来构造二叉搜索树。对于任意一个 i，它可以作为根节点，1 到 i-1 组成它的左子树，i+1 到 n 组成它的右子树。递归构造左子树和右子树，并将不同的子树组合起来。
状态定义：
- 对于区间
[start, end]，构造由该区间组成的所有二叉搜索树。 - 递归地将每个数字作为根节点，左子树由
[start, i-1]构造，右子树由[i+1, end]构造。 - 组合所有左子树和右子树，形成不同的二叉搜索树。
递推公式：
- 对于每个根节点
i，构造左子树generateTrees(start, i-1)和右子树generateTrees(i+1, end)。 - 将左右子树的所有组合与根节点
i连接，形成不同的树形结构。
终止条件：
- 当
start > end时，返回None，表示当前区间不能构成任何子树。
3. 解决方法
递归 + 动态规划方法：
- 定义递归函数
generateTrees(start, end)来构造[start, end]范围内的所有二叉搜索树。 - 对于每一个
i作为根节点，递归构造左子树和右子树，并将其组合。 - 最终返回所有构造的树。
伪代码：
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 = left
root.right = right
all_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 = left
root.right = right
all_trees.append(root)
return all_trees
return generateTrees(1, n)
Python代码解释
- 定义递归函数：
generateTrees(start, end)用于生成从start到end所有不同的二叉搜索树。 - 递归构造：对于每个
i作为根节点，递归构造左右子树的所有可能组合。 - 返回结果：最终返回所有可能的树形结构的根节点列表。
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++代码解释
- 定义递归函数：
generateTrees(start, end)用于生成从start到end所有不同的二叉搜索树。 - 递归构造：对于每个
i作为根节点，递归构造左右子树的所有可能组合。 - 返回结果：最终返回所有可能的树形结构的根节点列表。
总结
- 核心思想：通过递归和分治的思想，将问题分解为左右子树的组合问题。每个节点都可以作为根节点，递归构造其左子树和右子树，再组合这些树形结构。
- 复杂度分析：由于需要构造所有可能的树，时间复杂度较高，是 超指数级别 的问题。这类问题适合使用动态规划或递归解决，但无法避免高复杂度。
- 递归的应用：本问题是递归和分治思想的典型应用，尤其适合解决树形结构的构造问题。
原文地址：https://blog.csdn.net/AlbertDS/article/details/142892145
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！