谁能告诉我为什么下面的代码会占用内存: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));
}