Symmetric Tree

먼저 배열에서 이동하는 방법을 살펴보겠습니다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1에, 오른쪽 자식은 2*i+2에 있습니다. 자식은 해당 인덱스가 배열 안에 있고 그 위치의 값이 -1이 아닐 때만 실제 노드입니다. [1, 2, 2, 3, 4, 4, 3]에서 루트 1의 자식은 인덱스 1과 2에 있고, 인덱스 1의 2의 자식은 3과 4에 있습니다.

이제 한 번에 트리의 한 레벨씩 살펴보겠습니다. 좌우 대칭 이미지는 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 동일하므로, 빈 위치도 포함해 적은 각 레벨은 양방향으로 읽었을 때 같아야 합니다. 첫 번째 예시에서 루트 아래의 레벨은 2 2와 3 4 4 3입니다. 두 번째 예시에서는 2 2 다음에 -1 3 -1 3이 나오는데, 이를 뒤집으면 3 -1 3 -1이므로 답은 false입니다.

빈 위치도 해당 레벨에 남겨 두어야 합니다. 빈 위치를 제외하면 두 번째 예시의 마지막 레벨은 3 3이 되어 조건을 통과합니다. 해당 레벨에 있는 각 실제 노드의 자식 위치마다 항목을 하나씩 기록하고, 비어 있는 위치에는 -1을 기록합니다. 빈 위치의 자식도 비어 있으므로 아무것도 추가하지 않습니다. 각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 한 번에 한 레벨만 메모리에 유지하므로 가장 너비가 넓은 레벨의 너비를 w라 할 때 공간 복잡도는 O(w)입니다.

전체 레벨 대신 두 하위 트리를 비교합니다. 즉, 인덱스 1에서 시작하는 루트의 왼쪽 하위 트리와 인덱스 2에서 시작하는 오른쪽 하위 트리입니다. 두 위치가 모두 비어 있거나, 같은 값을 가지고 자식 노드가 서로 교차 대응하면 두 위치는 서로 대칭입니다. 한쪽의 왼쪽 자식은 다른 쪽의 오른쪽 자식과 대칭을 이루고(바깥쪽 쌍), 한쪽의 오른쪽 자식은 다른 쪽의 왼쪽 자식과 대칭을 이룹니다(안쪽 쌍).

첫 번째 예제에서 mirrors(1, 2)는 두 2를 비교한 다음, 바깥쪽 3들을 위해 mirrors(3, 6)을 호출하고 안쪽 4들을 위해 mirrors(4, 5)를 호출합니다. 두 호출은 각각 아래에 비어 있는 위치만 있는 것을 확인하고 true를 반환합니다. 두 번째 예제에서는 mirrors(4, 5)가 인덱스 4의 3과 인덱스 5의 빈 위치가 마주한 것을 확인하고 false를 반환합니다. 그러면 false가 최상위까지 거슬러 올라갑니다.

실제 노드 하나는 최대 하나의 쌍에만 속하므로 시간 복잡도는 O(n)입니다. 호출 스택의 깊이는 트리의 높이만큼인 O(h)이며, 여기서는 최대 14개 프레임입니다.

재귀에 필요한 것은 단 하나입니다. 아직 확인하지 않은 쌍입니다. 그 쌍들을 직접 스택에 저장하면 호출이 사라집니다. (1, 2) 쌍부터 시작합니다. 쌍을 꺼냅니다. 두 위치가 모두 비어 있으면 그 아래에는 아무것도 없으므로 다음으로 넘어갑니다. 한쪽이 비어 있거나 값이 다르면 트리는 대칭이 아닙니다. 그렇지 않으면 바깥쪽 쌍 (2*a+1, 2*b+2)과 안쪽 쌍 (2*a+2, 2*b+1)을 넣습니다.

쌍을 확인하는 순서는 중요하지 않습니다. 모든 쌍이 일치해야만 트리가 대칭이기 때문입니다. 스택을 사용하면 깊이 우선 순서로 확인하고, 큐를 사용하면 레벨 순서로 확인하며 같은 방식으로 작동합니다. 세 번째 예제에서는 처음으로 잘못된 쌍인 (3, 6)에서 멈추며, 이 쌍에는 5와 9가 들어 있습니다.

꺼내기 한 번마다 쌍 하나를 처리하고 각 실제 노드는 최대 한 쌍에만 포함되므로 시간 복잡도는 O(n)입니다. 스택에는 현재 경로의 레벨마다 대기 중인 쌍이 대략 하나씩 저장되므로 공간 복잡도는 O(h)이며, 걱정해야 할 재귀 제한도 없습니다.