# 不同的二叉搜索树

<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>

## template

```java
class Solution {
	public int numTrees(int n) {
		if (n < 2) {
			return 1;
		}

		int[] count = new int[n + 1];
		count[0] = 1;
		count[1] = 1;
		for (int i = 2; i <= n; i++) {
			int sum = 0;
			for (int root = 1; root <= i; root++) {
				sum = sum + count[root - 1] * count[i - root];
			}
			count[i] = sum;
		}

		return count[n];
	}
}

```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```