不同的二叉搜索树 II

用分治递归生成所有合法的二叉搜索树： 在区间[left, right]，我们依次选每个值i作为根节点，递归生成左子树区间和右子树区间的所有可能结构，再将左、右子树的所有组合与根节点拼接，得到当前区间的所有二叉搜索树。

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return dfs(1, n); // 从区间[1,n]开始递归
    }

    // 生成区间[left, right]对应的所有二叉搜索树
    vector<TreeNode*> dfs(int left, int right) {
        if (left > right) return {nullptr}; // 空树
        vector<TreeNode*> trees;

        // 选i作为当前根节点
        for (int i = left; i <= right; ++i) {
            // 递归生成左、右子树的所有可能
            vector<TreeNode*> l = dfs(left, i-1);
            vector<TreeNode*> r = dfs(i+1, right);
            
            // 与根i拼接
            for (TreeNode* lefttree : l) {
                for (TreeNode* righttree : r) {
                    TreeNode* root = new TreeNode(i);
                    root->left = lefttree;
                    root->right = righttree;
                    trees.push_back(root);//存入数组
                }
            }
        }
        return trees;
    }
};