# 不同的二叉搜索树 II
<div class="notranslate">
    <p>给你一个整数 <code>n</code> ，请你生成并返回所有由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的不同
        <strong>二叉搜索树</strong><em> </em>。可以按 <strong>任意顺序</strong> 返回答案。
    </p>

    <p>&nbsp;</p>

    <div class="original__bRMd">
        <div>
            <p><strong>示例 1：</strong></p>
            <img style="width: 600px; height: 148px;"
                src="https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg" alt="">
            <pre><strong>输入：</strong>n = 3
<strong><br />输出：</strong>[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
    </pre>

            <p><strong>示例 2：</strong></p>

            <pre><strong>输入：</strong>n = 1
<strong><br />输出：</strong>[[1]]
    </pre>

            <p>&nbsp;</p>

            <p><strong>提示：</strong></p>

            <ul>
                <li><code>1 &lt;= n &lt;= 8</code></li>
            </ul>
        </div>
    </div>
</div>
<p>以下错误的选项是？</p>

## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```
### after
```cpp

```

## 答案
```cpp
class Solution
{
public:
    vector<TreeNode *> generateTrees(int n)
    {
        if (n <= 0)
            return vector<TreeNode *>{};
        return generate(1, n);
    }

    vector<TreeNode *> generate(int begin, int end)
    {
        vector<TreeNode *> ret;
        if (begin > end)
        {
            return ret;
        }

        for (int i = begin; i <= end; ++i)
        {

            vector<TreeNode *> lSubs = generate(begin, i - 1);
            vector<TreeNode *> rSubs = generate(i + 1, end);
            for (auto l : lSubs)
            {
                for (auto r : rSubs)
                {
                    TreeNode *root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    ret.push_back(cloneTree(root));
                }
            }
        }

        return ret;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    vector<TreeNode *> generateTrees(int n)
    {
        vector<TreeNode *> res;
        if (n < 1)
            return res;
        res = creatTree(1, n);
        return res;
    }
    vector<TreeNode *> creatTree(int start, int end)
    {
        vector<TreeNode *> res;
        if (start > end)
        {
            res.push_back(NULL);
            return res;
        }
        if (start == end)
        {
            TreeNode *node = new TreeNode(start);
            res.push_back(node);
            return res;
        }
        for (int i = start; i <= end; i++)
        {
            vector<TreeNode *> left = creatTree(start, i - 1);
            vector<TreeNode *> right = creatTree(i + 1, end);
            for (int j = 0; j < left.size(); j++)
            {
                for (int k = 0; k < right.size(); k++)
                {
                    TreeNode *node = new TreeNode(i);
                    node->left = left[j];
                    node->right = right[k];
                    res.push_back(node);
                }
            }
        }
        return res;
    }
};
```

### B
```cpp
class Solution
{
public:
    vector<TreeNode *> m[9][9];

    vector<TreeNode *> generate(int left, int right)
    {
        if (left > right)
            return {nullptr};
        if (!m[left][right].empty())
            return m[left][right];

        vector<TreeNode *> trees;
        for (int i = left; i <= right; i++)
        {
            vector<TreeNode *> left_all = generate(left, i - 1);
            vector<TreeNode *> right_all = generate(i + 1, right);

            for (TreeNode *l : left_all)
            {
                for (TreeNode *r : right_all)
                {
                    TreeNode *root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    trees.emplace_back(root);
                }
            }
        }
        m[left][right] = trees;
        return trees;
    }

    vector<TreeNode *> generateTrees(int n)
    {
        return generate(1, n);
    }
};
```

### C
```cpp
class Solution
{
public:
    vector<TreeNode *> generateTrees(int n)
    {
        vector<TreeNode *> res;
        if (n == 0)
        {
            return res;
        }
        return gem(1, n);
    }
    vector<TreeNode *> gem(int start, int end)
    {
        vector<TreeNode *> res;
        if (start > end)
        {
            res.push_back(NULL);
        }
        for (int i = start; i <= end; i++)
        {
            vector<TreeNode *> lefts = gem(start, i - 1);
            vector<TreeNode *> rights = gem(i + 1, end);
            for (auto left : lefts)
            {
                for (auto right : rights)
                {
                    TreeNode *temp = new TreeNode(i);
                    temp->left = left;
                    temp->right = right;
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
};
```