1

谁能告诉我为什么下面的代码会占用内存：O(logN) + O(logM)？
代码是为了解决一个问题：给定大树T1，小树T2，检查T2是否是T1的子树。注意 size(T1)=N 和 size(T2)= M。事实上，除了 subtree() 和 matchTree() 的布尔结果之外，我没有看到任何额外的内存被占用。但是 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 回答