> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/96.-unique-binary-search-trees.md).

# 96. Unique Binary Search Trees

Given an integer `n`, return *the number of structurally unique **BST'**s (binary search trees) which has exactly* `n` *nodes of unique values from* `1` *to* `n`.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)

```
Input: n = 3
Output: 5
```

**Example 2:**

```
Input: n = 1
Output: 1
```

 

**Constraints:**

* `1 <= n <= 19`

### Solution:

这就是一个正宗的穷举问题，那么什么方式能够正确地穷举合法 BST 的数量呢？

我们前文说过，不要小看「穷举」，这是一件看起来简单但是比较有技术含量的事情，问题的关键就是不能数漏，也不能数多，你咋整？

之前 [手把手刷二叉树第一期](http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==\&mid=2247487126\&idx=1\&sn=4de13e66397bc35970963c5a1330ce18\&chksm=9bd7f09eaca0798853c41fba05ad5fa958b31054eba18b69c785ae92f4bd8e4cc7a2179d7838\&scene=21#wechat_redirect) 说过，二叉树算法的关键就在于明确根节点需要做什么，其实 BST 作为一种特殊的二叉树，核心思路也是一样的。

举个例子，比如给算法输入`n = 5`，也就是说用`{1,2,3,4,5}`这些数字去构造 BST。

首先，这棵 BST 的根节点总共有几种情况？

显然有 5 种情况对吧，因为每个数字都可以作为根节点。

比如说我们固定`3`作为根节点，这个前提下能有几种不同的 BST 呢？

根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。

所以如果固定`3`作为根节点，左子树节点就是`{1,2}`的组合，右子树就是`{4,5}`的组合。

**左子树的组合数和右子树的组合数乘积**就是`3`作为根节点时的 BST 个数。

![](/files/zydDrKDjngE3pqCnXR0I)

我们这是说了`3`为根节点这一种特殊情况，其实其他的节点也是一样的。

那你可能会问，我们可以一眼看出`{1,2}`和`{4,5}`有几种组合，但是怎么让算法进行计算呢？

其实很简单，只需要递归就行了，我们可以写这样一个函数：

```
// 定义：闭区间 [lo, hi] 的数字能组成 count(lo, hi) 种 BST
int count(int lo, int hi);
```

根据这个函数的定义，结合刚才的分析，可以写出代码：

```
/* 主函数 */int numTrees(int n) {    
// 计算闭区间 [1, n] 组成的 BST 个数    
return count(1, n);}
/* 计算闭区间 [lo, hi] 组成的 BST 个数 */
int count(int lo, int hi) {    
// base case    
if (lo > hi) return 1;    
int res = 0;    
for (int i = lo; i <= hi; i++) 
{        
// i 的值作为根节点 root        
int left = count(lo, i - 1);        
int right = count(i + 1, hi);        
// 左右子树的组合数乘积是 BST 的总数       
 res += left * right;    
 }    
 return res;
 }
```

注意 base case，显然当`lo > hi`闭区间`[lo, hi]`肯定是个空区间，也就对应着空节点 null，虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0。

这样，题目的要求已经实现了，但是时间复杂度非常高，肯定存在重叠子问题。

前文动态规划相关的问题多次讲过消除重叠子问题的方法，无非就是加一个备忘录：

```
// 备忘录int[][] memo;
int numTrees(int n) 
{    
// 备忘录的值初始化为 0    
memo = new int[n + 1][n + 1];    
return count(1, n);
}
int count(int lo, int hi) 
{    if (lo > hi) return 1;    
// 查备忘录    
if (memo[lo][hi] != 0) 
{        return memo[lo][hi];    }   
 int res = 0;    
 for (int mid = lo; mid <= hi; mid++) 
 {       
   int left = count(lo, mid - 1);       
   int right = count(mid + 1, hi);      
    res += left * right;    
 }    
   // 将结果存入备忘录    
   memo[lo][hi] = res;   
   return res;
 }
```

这样，这道题就完全解决了。