作者:
illl (ill!)
2015-03-12 10:51:32小弟想請問這個的時間和空間複雜度
題目是給你一個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;
}