# 0096. 不同的二叉搜索树

## 题目地址（96. 不同的二叉搜索树）

<https://leetcode-cn.com/problems/unique-binary-search-trees/>

## 题目描述

```
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
```

## 前置知识

* 二叉搜索树
* 分治

## 公司

* 阿里
* 腾讯
* 百度
* 字节

## 岗位信息

* 腾讯（广州）- 安卓 - 社招 - 三面

## 思路

这是一个经典的使用分治思路的题目。

对于数字 n ，我们可以 1- n 这样的离散整数分成左右两部分。我们不妨设其分别为 A 和 B。那么问题转化为 A 和 B 所能组成的 BST 的数量的笛卡尔积。而对于 A 和 B 以及原问题除了规模，没有不同，这不就是分治思路么？至于此，我们只需要考虑边界即可，边界很简单就是 n 小于等于 1 的时候，我们返回 1。

具体来说：

* 生成一个\[1:n + 1] 的数组
* 我们遍历一次数组，对于每一个数组项，我们执行以下逻辑
* 对于每一项，我们都假设其是断点。断点左侧的是 A，断点右侧的是 B。
* 那么 A 就是 i - 1 个数， 那么 B 就是 n - i 个数
* 我们递归，并将 A 和 B 的结果相乘即可。

> 其实我们发现，题目的答案只和 n 有关，和具体 n 个数的具体组成，只要是有序数组即可。

题目没有明确 n 的取值范围，我们试一下暴力递归。

代码（Python3）：

```python
class Solution:
    def numTrees(self, n: int) -> int:
        if n <= 1:
            return 1
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        return res
```

上面的代码会超时，并没有栈溢出，因此我们考虑使用 hashmap 来优化，代码见下方代码区。

## 关键点解析

* 分治法
* 笛卡尔积
* 记忆化递归

## 代码

语言支持：Python3, CPP

Python3 Code:

```python
class Solution:
    visited = dict()

    def numTrees(self, n: int) -> int:
        if n in self.visited:
            return self.visited.get(n)
        if n <= 1:
            return 1
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res
```

CPP Code:

```cpp
class Solution {
    vector<int> visited;
    int dp(int n) {
        if (visited[n]) return visited[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += dp(i) * dp(n - i - 1);
        return visited[n] = ans;
    }
public:
    int numTrees(int n) {
        visited.assign(n + 1, 0);
        visited[0] = 1;
        return dp(n);
    }
};
```

**复杂度分析**

* 时间复杂度：一层循环是 N，另外递归深度是 N，因此总的时间复杂度是 $O(N^2)$
* 空间复杂度：递归的栈深度和 visited 的大小都是 N，因此总的空间复杂度为 $O(N)$

## 相关题目

* [95.unique-binary-search-trees-ii](https://github.com/azl397985856/leetcode/blob/master/problems/95.unique-binary-search-trees-ii.md)

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 30K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/96.unique-binary-search-trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.