作者illl (ill!)
看板Prob_Solve
标题[问题] 请问这个的时间和空间复杂度
时间Thu Mar 12 10:51:32 2015
小弟想请问这个的时间和空间复杂度
题目是给你一个n
要你把1~n所有可能的Binary Search Tree给列出来
我是用递回(qq)找
每一个递回有三个for loop
第一个for loop是要列出那个范围所有的node
剩下两个是把左边和右边的child node街上去
感恩
public List<TreeNode> generateTrees(int n) {
return qq(1,n);
}
List<TreeNode> qq(int first, int last){
List<TreeNode> res= new ArrayList<TreeNode>();
if(first>last) {
res.add(null);
return res;
}
for(int i=first; i<=last; i++){
List<TreeNode> left=qq(first, i-1);
List<TreeNode> right=qq(i+1, last);
for(TreeNode leftti: left){
for(TreeNode rightti: right){
TreeNode temp= new TreeNode(i);
temp.left=leftti;
temp.right=rightti;
res.add(temp);
}
}
}
return res;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 130.65.251.52
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1426128695.A.B2A.html
※ 编辑: illl (130.65.251.52), 03/12/2015 10:53:10
1F：→ yr: 1~n所有可能的Binary Search Tree <-- 可否定义一下这个？03/12 16:04
http://tinyurl.com/pqekbca
这是题目里面有图，
总共有n个node，值分别是1~n，列出所有可能的组合
※ 编辑: illl (172.56.17.46), 03/12/2015 16:13:53
2F：→ yr: 这题只要算出数量就好，不用列出来，你是要列出来吗 03/12 17:17
3F：→ illl: 我想要列出来，感恩 03/12 17:31
4F：→ yr: 稍微分析一下，用猜的 time: O(n^n) space: O(n^(n+1)) 03/12 21:29
5F：→ illl: 多谢！ 03/13 02:07