# 不同的二叉搜索树

<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://img-service.csdnimg.cn/img_convert/afa8711beb3c6f3c54d039379f525fb7.jpeg"
        alt="">
    <pre><strong>输入：</strong>n = 3
<strong>输出：</strong>5
    </pre>

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

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

    <p>&nbsp;</p>

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

    <ul>
        <li><code>1 &lt;= n &lt;= 19</code></li>
    </ul>
</div>

以下程序实现了这一功能，请你填补空白处内容：

```cpp
#include <stdc++.h>
using namespace std;
class Solution
{
public:
	int numTrees(int n)
	{
		vector<int> sum(n + 1);
		sum[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < i; j++)
			{
				___________________;
			}
		}
		return sum[n];
	}
}
```

## template

```cpp
#include <stdc++.h>
using namespace std;
class Solution
{
public:
	int numTrees(int n)
	{
		vector<int> sum(n + 1);
		sum[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < i; j++)
			{
				sum[i] += sum[j] * sum[i - j - 1];
			}
		}
		return sum[n];
	}
}
```

## 答案

```cpp
sum[i] += sum[j] * sum[i - j - 1];
```

## 选项

### A

```cpp
sum[i] += sum[j] * sum[i - j];
```

### B

```cpp
sum[i] += sum[j] * sum[j - i - 1];
```

### C

```cpp
sum[i] += sum[j] * sum[j - i];
```