# 不同的二叉搜索树

<div class="notranslate">
    <p>给你一个整数 <code>n</code> ，求恰由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的 <strong>二叉搜索树</strong>
        有多少种？返回满足题意的二叉搜索树的种数。</p>

    <p>&nbsp;</p>

    <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>5
    </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;= 19</code></li>
    </ul>
</div>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
class Solution
{
public:
    int numTrees(int n)
    {
        if (n < 1)
        {
            return 0;
        }
        return numTrees(1, n);
    }
    int numTrees(int begin, int end)
    {
        if (begin > end)
        {
            return 1;
        }
        int sum = 0;
        for (int i = begin; i <= end; i++)
        {
            int left = numTrees(begin, i);
            int right = numTrees(i + 1, end);
            sum += left * right;
        }
        return sum;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    int numTrees(int n)
    {
        if (n < 2)
            return 1;
        else if (n == 3)
            return 5;
        else if (n == 4)
            return 14;
        else if (n == 5)
            return 42;
        else
        {
            int i, sum = 0, left, right;
            for (i = 0; i < n; i++)
            {
                left = i;
                right = n - i - 1;
                sum += numTrees(left) * numTrees(right);
            }
            return sum;
        }
    }
};
```

### B

```c
class Solution
{
public:
    int numTrees(int n)
    {
        if (n < 2)
            return 1;
        else
        {
            int i, sum = 0, left, right;
            for (i = 0; i < n; i++)
            {
                left = i;
                right = n - i - 1;
                sum += numTrees(left) * numTrees(right);
            }
            return sum;
        }
    }
};
```

### C

```c
class Solution
{
public:
    int numTrees(int n)
    {
        int dp[n + 1];
        memset(dp, 0, sizeof(dp));
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};
```