LeetCode] 动态编程 - 95.动态编程 - 95.不同的二叉搜索树 II（附完整 Python/C++ 代码） - 基本思想

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问题的基本思路。

---