0
따라서이 프로그램은 btree의 대칭을 결정합니다. 저를 혼란스럽게하는 것은 checkSymmetric이 같은 줄에서 두 번 호출된다는 것입니다. 그래서 우리가 checkSymmetric을 호출 할 때마다 호출 스택에 두 개의 새로운 스택 프레임을 추가해야한다는 뜻은 아니겠습니까? 만약 우리가 O (2^h)의 공간 복잡성을 가지고 있지 않다면?왜이 프로그램의 공간 복잡성은 O (h)입니까? 여기서 h는 btree의 높이입니다.
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;
}