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

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

# 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)

/**
 * 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;
    }
};