95.unique-binary-search-trees-ii.md

题目地址（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一样。

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

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

关键点解析

• 分治法

代码

语言支持：Python3, CPP

Python3 Code:

classSolution: defgenerateTrees(self, n: int) ->List[TreeNode]: ifnotn: return [] defgenerateTree(start, end): ifstart>end: return [None] res= [] foriinrange(start, end+1): ls=generateTree(start, i-1) rs=generateTree(i+1, end) forlinls: forrinrs: node=TreeNode(i) node.left=lnode.right=rres.append(node) returnresreturngenerateTree(1, n)

CPP Code:

classSolution { 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(newTreeNode(i)); v.back()->left = left; v.back()->right = right; } } } return v; } public: vector<TreeNode*> generateTrees(int n) { if (n <= 0) return {}; returngenerateTrees(1, n); } };

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

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

相关题目

• 96.unique-binary-search-trees