# 0095. 不同的二叉搜索树 II ## 题目地址（95. 不同的二叉搜索树 II） <https://leetcode-cn.com/problems/unique-binary-search-trees-ii/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个整数 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](96.unique-binary-search-trees.html)一样。 只是我们需要求解的不仅仅是数字，而是要求解所有的组合。我们假设问题 f(1, n) 是求解 1 到 n（两端包含）的所有二叉树。那么我们的目标就是求解 f(1, n)。 我们将问题进一步划分为子问题，假如左侧和右侧的树分别求好了，我们是不是只要运用组合的原理，将左右两者进行做和就好了，我们需要两层循环来完成这个过程。 ## 关键点解析 - 分治法 ## 代码 - 语言支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">generateTrees</span><span class="hljs-params">(self, n: int)</span> -> List[TreeNode]:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> n: <span class="hljs-keyword">return</span> [] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">generateTree</span><span class="hljs-params">(start, end)</span>:</span> <span class="hljs-keyword">if</span> start > end: <span class="hljs-keyword">return</span> [<span class="hljs-keyword">None</span>] res = [] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(start, end + <span class="hljs-params">1</span>): ls = generateTree(start, i - <span class="hljs-params">1</span>) rs = generateTree(i + <span class="hljs-params">1</span>, end) <span class="hljs-keyword">for</span> l <span class="hljs-keyword">in</span> ls: <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> rs: node = TreeNode(i) node.left = l node.right = r res.append(node) <span class="hljs-keyword">return</span> res <span class="hljs-keyword">return</span> generateTree(<span class="hljs-params">1</span>, n) ``` ``` ## 相关题目 - [96.unique-binary-search-trees](96.unique-binary-search-trees.html)