java - 为什么该程序的空间复杂度为O(h)？其中h是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;
}

最佳答案

请注意，我们会帮忙的，但实际上我们不会帮你做作业。
让我困惑的是，checkSymmetric在同一行中被调用了两次所以，这不意味着每次调用checksymmetric时，我们必须在调用堆栈中添加两个新的堆栈帧吗？
不，因为这两个调用是顺序的，而不是并行的根据定义，执行一个调用的所有资源都是在第二个调用之前释放的——它们并不是同时保存的这当然包括所有涉及的堆栈帧。
如果是这样的话，我们是否有O（2 ^ h）空间复杂度？
事实并非如此，那么这会告诉你什么是空间复杂性呢？