[問題] 請問這個的時間和空間複雜度

[illl (ill!)]

小弟想請問這個的時間和空間複雜度
題目是給你一個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
→ yr: 1~n所有可能的Binary Search Tree <-- 可否定義一下這個？
http://tinyurl.com/pqekbca
這是題目裡面有圖，
總共有n個node，值分別是1~n，列出所有可能的組合
※ 編輯: illl (172.56.17.46), 03/12/2015 16:13:53
→ yr: 這題只要算出數量就好，不用列出來，你是要列出來嗎
→ illl: 我想要列出來，感恩
→ yr: 稍微分析一下，用猜的 time: O(n^n) space: O(n^(n+1))
→ illl: 多謝！