次のコードにおいて、計算量の算出ってどのように行うのでしょうか?
O(N)の計算時間なのですが、これがどのように算出したのかが分かりません。
二分探索木が与えられた時、同じ深さのノード同士の連結リストを作るアルゴリズムを設計してください。(例えば、深さDの木がある時、D個の連結リストを作ることになります。)
Java
1void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, 2 int level) { 3 if(root == null) return; 4 5 LinkedList<TreeNode> list = null; 6 if(lists.size() == level) { //この深さがまだリストに含まれていない 7 list = new LinkedList<TreeNode>(); 8 /*深さは探索が進むに従って増加する。 9 従って、深さiの頂点に初めて到達した時、 10 深さ0〜i-1の頂点にのみ到達している。 11 なので、深さiのために新しいリストを作って追加すれば良い */ 12 13 lists.add(list); 14 } else { 15 list = lists.get(level); 16 } 17 list.add(root); 18 createLevelLinkedList(root.left, lists, level + 1); 19 createLevelLinkedList(root.right, lists, level + 1); 20 } 21 22 ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) { 23 ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>(); 24 createLevelLinkedList(root, lists, 0); 25 return lists; 26 }
コード中に再帰があるので、漸化式を使ったりするみたいですが、この場合どのような漸化式になるのでしょうか?
お分かりの方、おたすけください。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。