95. Unique Binary Search Trees II

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n==0) return vector<TreeNode*>();
        return genTree(1, n);
    }
    
    vector<TreeNode*> genTree(int start, int end) {
		// start ~ end 的所有生成树
        vector<TreeNode*> tree_list;
        if (start>end) tree_list.push_back(NULL);
        
        for(int i=start;i<=end;++i) {
			// 每一个都可以作为根
			// 递归生成左子树
            vector<TreeNode*> left = genTree(start, i-1);
			// 递归生成右子树
            vector<TreeNode*> right = genTree(i+1, end);

			// 左右子树以 i 为根可以组合处很多棵树
            for(auto lnode : left) {
                for(auto rnode : right) {
                    TreeNode* root = new TreeNode(i);
                    root->left = lnode;
                    root->right = rnode;
					// 添加进结果并返回
                    tree_list.push_back(root);
                }
            }
        }
        return tree_list;
    }
};