Leetcode No.95 不同的二叉搜索树 II
一、题目描述
给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1: 输入:n = 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2: 输入:n = 1 输出:[[1]]
提示: 1 <= n <= 8
二、解题思路
二叉搜索树关键的性质是根节点的值大于左子树所有节点的值,小于右子树所有节点的值,且左子树和右子树也同样为二叉搜索树。因此在生成所有可行的二叉搜索树的时候,假设当前序列长度为 n,如果我们枚举根节点的值为 i,那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为[1…i−1],右子树的节点值的集合为[i+1…n]。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题,因此我们可以想到用回溯的方法来解决这道题目。
我们定义 generateTrees(start, end) 函数表示当前值的集合为[start,end],返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路,我们考虑枚举[start,end] 中的值 i 为当前二叉搜索树的根,那么序列划分为了 [start,i−1] 和[i+1,end] 两部分。我们递归调用这两部分,即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end),获得所有可行的左子树和可行的右子树,那么最后一步我们只要从可行左子树集合中选一棵,再从可行右子树集合中选一棵拼接到根节点上,并将生成的二叉搜索树放入答案数组即可。
递归的入口即为 generateTrees(1, n),出口为当 start>end 的时候,当前二叉搜索树为空,返回空节点即可。
三、代码
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<TreeNode>();
}
return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> allTrees = new LinkedList<TreeNode>();
if (start > end) {
allTrees.add(null);
return allTrees;
}
// 枚举可行根节点
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
List<TreeNode> leftTrees = generateTrees(start, i - 1);
// 获得所有可行的右子树集合
List<TreeNode> rightTrees = generateTrees(i + 1, end);
// 从左子树集合中选出一棵左子树,从右子树集合中选出一棵右子树,拼接到根节点上
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode currTree = new TreeNode(i);
currTree.left = left;
currTree.right = right;
allTrees.add(currTree);
}
}
}
return allTrees;
}
}
四、复杂度分析
时间复杂度:整个算法的时间复杂度取决于「可行二叉搜索树的个数」,而对于 n 个点生成的二叉搜索树数量等价于数学上第 n 个「卡特兰数」,用 Gn表示。卡特兰数具体的细节请读者自行查询,这里不再赘述,只给出结论。生成一棵二叉搜索树需要 O(n)的时间复杂度,一共有 Gn棵二叉搜索树,也就是 O(n*Gn)。而卡特兰数以(4^n)/(n^(3/2)增长,因此总时间复杂度为O((4^n)/(n^(1/2))。
空间复杂度:n 个点生成的二叉搜索树有G_n棵,每棵有 n 个节点,因此存储的空间需要 O(n*Gn)=O((4^n)/(n^(1/2)) ,递归函数需要 O(n)的栈空间,因此总空间复杂度为O((4^n)/(n^(1/2)) 。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十