# 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](/leetcode-solution/medium/96.unique-binary-search-trees.md)一样。

只是我们需要求解的不仅仅是数字，而是要求解所有的组合。我们假设问题 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](/leetcode-solution/medium/96.unique-binary-search-trees.md)


---

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