所以这个程序决定了一个btree的对称性。 令我困惑的是 checkSymmetric 在同一行中被调用了两次。那么这是否意味着我们必须为每次调用 checkSymmetric 向调用堆栈添加两个新的堆栈帧？如果是这样的话，我们不应该有 O(2^h) 的空间复杂度吗？
public static boolean isSymmetric(BinaryTreeNode<Integer> tree) {
return tree == null || checkSymmetric(tree.left, tree.right);
}
private static boolean checkSymmetric(BinaryTreeNode<Integer> subtree0,
BinaryTreeNode<Integer> subtree1) {
if (subtree0 == null && subtree1 == null) {
return true;
} else if (subtree0 != null && subtree1 != null) {
return subtree0.data == subtree1.data
&& checkSymmetric(subtree0.left, subtree1.right)
&& checkSymmetric(subtree0.right, subtree1.left);
}
// One subtree is empty, and the other is not.
return false;
}
最佳答案
请注意，我们会提供帮助，但实际上我们不会为您做功课。
What is confusing me is that checkSymmetric is called twice in the same line. So wouldnt that mean we have to add two new stack frames to our callstack for each call to checkSymmetric?
不是，因为这两个调用是顺序的，不是并行的。根据定义，在第二次调用之前释放一次调用执行范围内的所有资源——它们并非同时持有。这当然包括所有涉及的堆栈帧。
If thats the case shouldnt we have O(2^h) space complexity?
事实并非如此，那么关于空间复杂度，这说明了什么？
关于java - 为什么这个程序的空间复杂度是O(h)？其中 h 是 btree 的高度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46457771/