> 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/95.-unique-binary-search-trees-ii-m.md).

# 95. Unique Binary Search Trees II (M)

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

 

**Example 1:**

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

```
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
```

**Example 2:**

```
Input: n = 1
Output: [[1]]
```

 

**Constraints:**

* `1 <= n <= 8`

### Solution:

<https://www.jiuzhang.com/problem/unique-binary-search-trees-ii/>

**明白了上道题构造合法 BST 的方法，这道题的思路也是一样的**：

1、穷举`root`节点的所有可能。

2、递归构造出左右子树的所有合法 BST。

3、给`root`节点穷举所有左右子树的组合。

由于二叉查找树的性质，对于一个二叉查找树的节点，它的左子树中所有节点的值都小于它的值，它的右子树中所有节点的值都大于它的值。而且二叉查找树的中序遍历是一个排好序的数组。

我们可以枚举根节点的所有可能的值。如果根节点的值等于ii，那么左子树的节点值在范围[1,i−1](https://www.jiuzhang.com/problem/unique-binary-search-trees-ii/)内，右子树节点的值在范围[i+1,n](https://www.jiuzhang.com/problem/unique-binary-search-trees-ii/)中。遍历左子树的所有情况和右子树的所有情况，就可以组合出当根节点的值等于ii时的所有情况。

根据以上的推导，我们可以发现这是一个明显的递归结构，左右子树也可以用这个递归结构构造。那么我们就可以用递归来解决这个问题。

#### 代码思路

递归的步骤：

1、递归出口，如果start值大于end值，返回一个只含空节点的列表。

2、枚举根节点的值root\_val，从start到end。

3、递归获得所有可能的左子树[start, root\_val - 1](https://www.jiuzhang.com/problem/unique-binary-search-trees-ii/)。

4、递归获得所有可能的右子树[root\_val + 1, end](https://www.jiuzhang.com/problem/unique-binary-search-trees-ii/)。

5、遍历左右子树的所有可能，组合成新的树，加入结果数组result中。

6、返回结果数组result。

#### 复杂度分析

设二叉查找树的节点数为NN。 C(n)=(2n)!/(n!(n+1)!)为卡特兰数第n项的计算公式。 所有不同的节点数为NN的二叉查找树为对应的卡特兰数C(N)。

**时间复杂度：O(N∗C(N))**

由于有的子树会被重复计算，时间复杂度为O(N∗C(N))。

**空间复杂度：O(N)**

空间复杂度取决于树的最大深度，O(N)。

#### 源代码

javapythonc++

```
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    public List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }
    // 返回值是从start到end的所有可能的二叉查找树
    public List<TreeNode> helper(int start, int end) {
        List<TreeNode> result = new ArrayList<>();

        // 递归出口
        if (start > end) {
            result.add(null);
            return result;
        }
        
        // 枚举根节点的值
        for (int rootVal = start; rootVal <= end; rootVal++) {
            // 递归获得所有可能的左子树
            List<TreeNode> leftTrees = helper(start, rootVal - 1);
            // 递归获得所有可能的右子树
            List<TreeNode> rightTrees = helper(rootVal + 1, end);
            // 枚举每一种左右子树的组合，组成新的二叉树
            for (int i = 0; i < leftTrees.size(); i++) {
                TreeNode leftTree = leftTrees.get(i);
                for (int j = 0; j < rightTrees.size(); j++) {
                    TreeNode rightTree = rightTrees.get(j);
                    TreeNode root = new TreeNode(rootVal);
                    root.left = leftTree;
                    root.right = rightTree;
                    result.add(root);
                }
            }
        }
        return result;
    }
}
```