【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 = 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代码解释

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. 返回结果：最终返回所有可能的树形结构的根节点列表。

总结

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