1

O(logN) + O(logM) というコードがメモリを消費する理由を教えてください。
コードは問題を解決することです: 大きな木 T1、小さな木 T2 が与えられたとき、T2 が T1 の部分木かどうかをチェックします。size(T1)=N および size(T2)= M に注意してください。実際、subtree() と matchTree() の bool の結果を除いて、追加のメモリが消費されることはありませんでした。しかし、IMO このメモリは O(1) である必要があります。間違っている場合は修正してください。

boolean containsTree(TreeNode t1, TreeNode t2) {
  if (t2 == null) return true; // The empty tree is always a subtree
  else return subTree(t1, t2);
}

boolean subTree(TreeNode r1, TreeNode r2) {
  if (r1 == null)
   return false; // big tree empty & subtree still not found.
  if (r1.data == r2.data) {
    if (matchTree(r1,r2)) return true;
  }
  return (subTree(r1.left, r2) || subTree(r1.right, r2));
}

boolean matchTree(TreeNode r1, TreeNode r2) {
 if (r2 == null && r1 == null)
     return true; // nothing left in the subtree
 if (r1 == null || r2 == null)
     return false; // big tree empty & subtree still not found
 if (r1.data != r2.data)
     return false; // data doesn’t match
 return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right));
}
4

2 に答える 2

3

関数はそれ自体を再帰的に呼び出すため、メモリを明示的に使用していなくても、スタックはコール スタックで O(h1) + O(h2) のコストがかかります。ツリーが十分にバランスが取れている場合、これは O(logn) + O(logm) と同じです。

于 2013-07-03T23:34:36.197 に答える
1

再帰はスタック スペースを必要とします。それはあなたが探しているものですか?

于 2013-07-03T23:34:50.243 に答える