[問題] 請問這個的時間和空間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者illl (ill!)時間9年前 (2015/03/12 10:51)推噓0(0推 0噓 5→)留言5則, 2人參與討論串1/1
小弟想請問這個的時間和空間複雜度
題目是給你一個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://www.ptt.cc/bbs/Prob_Solve/M.1426128695.A.B2A.html
※ 編輯: illl (130.65.251.52), 03/12/2015 10:53:10
→
03/12 16:04, , 1F
03/12 16:04, 1F
http://tinyurl.com/pqekbca
這是題目裡面有圖，
總共有n個node，值分別是1~n，列出所有可能的組合
※ 編輯: illl (172.56.17.46), 03/12/2015 16:13:53
→
03/12 17:17, , 2F
03/12 17:17, 2F
→
03/12 17:31, , 3F
03/12 17:31, 3F
→
03/12 21:29, , 4F
03/12 21:29, 4F
→
03/13 02:07, , 5F
03/13 02:07, 5F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
