# 0095. 不同的二叉搜索树 II

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

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

## 题目描述

```
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

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

## 前置知识

* 二叉搜索树
* 分治

## 公司

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

## 思路

这是一个经典的使用分治思路的题目。基本思路和[96.unique-binary-search-trees](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/96.unique-binary-search-trees)一样。

只是我们需要求解的不仅仅是数字，而是要求解所有的组合。我们假设问题 f(1, n) 是求解 1 到 n（两端包含）的所有二叉树。那么我们的目标就是求解 f(1, n)。

我们将问题进一步划分为子问题，假如左侧和右侧的树分别求好了，我们是不是只要运用组合的原理，将左右两者进行合并就好了，我们需要两层循环来完成这个过程。

## 关键点解析

* 分治法

## 代码

语言支持：Python3, CPP

Python3 Code:

```python
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if not n:
            return []

        def generateTree(start, end):
            if start > end:
                return [None]
            res = []
            for i in range(start, end + 1):
                ls = generateTree(start, i - 1)
                rs = generateTree(i + 1, end)
                for l in ls:
                    for r in rs:
                        node = TreeNode(i)
                        node.left = l
                        node.right = r
                        res.append(node)

            return res

        return generateTree(1, n)
```

CPP Code:

```cpp
class Solution {
private:
    vector<TreeNode*> generateTrees(int first, int last) {
        if (first > last) return { NULL };
        vector<TreeNode*> v;
        for (int i = first; i <= last; ++i) {
            auto lefts = generateTrees(first, i - 1);
            auto rights = generateTrees(i + 1, last);
            for (auto left : lefts) {
                for (auto right : rights) {
                    v.push_back(new TreeNode(i));
                    v.back()->left = left;
                    v.back()->right = right;
                }
            }
        }
        return v;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n <= 0) return {};
        return generateTrees(1, n);
    }
};
```

**复杂度分析** 令 C(N) 为 N 的卡特兰数。

* 时间复杂度：$O(N\*C(N))$
* 空间复杂度：$O(C(N))$

## 相关题目

* [96.unique-binary-search-trees](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/96.unique-binary-search-trees)