思路
参考自详细通俗的思路分析，多解法
利用查找二叉树的性质。左子树的所有值小于根节点，右子树的所有值大于根节点。
所以如果求 1…n 的所有可能。
我们只需要把 1 作为根节点，[ ] 空作为左子树，[ 2 … n ] 的所有可能作为右子树。
2 作为根节点，[ 1 ] 作为左子树，[ 3…n ] 的所有可能作为右子树。
3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[ 4 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
4 作为根节点，[ 1 2 3 ] 的所有可能作为左子树，[ 5 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
…
n 作为根节点，[ 1… n ] 的所有可能作为左子树，[ ] 作为右子树。
至于，[ 2 … n ] 的所有可能以及 [ 4 … n ] 以及其他情况的所有可能，可以利用上边的方法，把每个数字作为
根节点，然后把所有可能的左子树和右子树组合起来即可。
特判情况
如果是n==0，那就返回 null。
递归边界
-
如果只有一个数字，那么所有可能就是一种情况，把该数字作为一棵树。
-
如果start<end，则说明此时没有数字，将null加入结果中
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ans;
//此时没有数字，将null加入结果中
if (n == 0) return ans;
return getAns(1, n);
}
private:
vector<TreeNode*> getAns(int start, int end)
{
vector<TreeNode*> ans;
//此时没有数字，将null加入结果中
if (start > end) {
ans.push_back(nullptr);
return ans;
}
//只有一个数字，当前数字作为一颗树加入到结果中
if (start==end)
{
TreeNode* tree = new TreeNode(start);
ans.push_back(tree);
return ans;
}
//尝试每个数组作为根节点
for (int i=start;i<=end;i++)
{
//得到所有可能的左子树
vector<TreeNode*> leftTrees = getAns(start, i - 1);//左子树的所有值小于根节点
//得到所有可能的右子树
vector<TreeNode*> rightTrees = getAns(i + 1, end);//右子树的所有值大于根节点
//左子树右子树两两组合
for (TreeNode* leftTree:leftTrees)
{
for (TreeNode* rightTree:rightTrees)
{
TreeNode* root = new TreeNode(i);
root->left = leftTree;
root->right = rightTree;
//加入到最终结果中
ans.push_back(root);
}
}
}
return ans;
}
};