95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 示例： 输入：3 输出： [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释： 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 提示：

• 0 <= n <= 8

解题思路

递归 深度优先 二叉搜索树 创建二叉树
i 从 start 到 end,
[start,i-1] 作为 i 的左子树， [i+1,end] 作为 i 的右子树
左子树，右子树向下递归
递归终止条件 start > end , 返回 NULL
每一层以 i 作为根结点，新建根结点， [start,i-1] 作为 i 的左子树， [i+1,end] 作为 i 的右子树

例子：
[1 2]
null 2
null null
———————-
1
null 2
null null
———————-
1 null
null null
——————-
2
1 null
null null

class Solution {
public:
    vector<TreeNode*> getTrees(int start,int end) {
        if(start > end) return {NULL};
        vector<TreeNode*> res;//局部变量
        // [start,i-1] 作为 i 的左子树， [i+1,end] 作为 i 的右子树，
        for(int i = start;i <= end; i++) {
            vector<TreeNode*> leftSubTree = getTrees(start,i-1);
            vector<TreeNode*> rightSubTree = getTrees(i+1,end);
    //从多种左子树中选一个作为根结点的左子树，从多种右子树中选一个作为根结点的右子树，
            for(auto& left:leftSubTree) {
                for(auto& right:rightSubTree) {
                    TreeNode* curNode = new TreeNode(i);
                    curNode->left = left;
                    curNode->right = right;
                    res.push_back(curNode); 
                }
            }
        }
        return res;
    }
    vector<TreeNode*> generateTrees(int n) {
       if(!n) return {};
       return getTrees(1,n);
    }
};