LeetCode 95. 不同的二叉搜索树 II（递归）

示例:
输入: 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

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0)
        	return {};
        return generateTrees(1,n);
    }

    vector<TreeNode*> generateTrees(int start, int end)
    {
    	vector<TreeNode*> ans;
    	if(start > end)
    	{
    		ans.push_back(NULL);
    		return ans;
    	}
    	vector<TreeNode*> subLeft, subRight;
    	TreeNode *node;
    	for(int i = start; i <= end; i++)
    	{
    		subLeft = generateTrees(start,i-1);
    		subRight = generateTrees(i+1,end);
    		for(TreeNode* l : subLeft)
    			for(TreeNode* r : subRight)
    			{
    				node = new TreeNode(i);
    				node->left = l;
    				node->right = r;
    				ans.push_back(node);
    			}
    	}
    	return ans;
    }
};