문제 개요
두 개의 이진 트리가 주어졌을 때, 임의의 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리를 원하는 횟수만큼 자유롭게 교환할 수 있다고 가정해 보겠습니다. 이 조건에서 첫 번째 트리를 두 번째 트리와 완전히 동일한 형태로 변환할 수 있는지 판별하는 것이 이번 문제의 핵심입니다.
예를 들어 아래 그림과 같은 두 트리가 입력으로 주어졌다고 합시다.
루트의 자식뿐 아니라 하위 노드들의 좌우 자식까지 적절히 뒤집으면 두 트리를 같은 구조로 만들 수 있으므로, 출력 결과는 True입니다.
해결 접근 방식
이 문제는 레벨 순서 탐색(BFS)으로 깔끔하게 해결할 수 있습니다. 트리를 위에서부터 한 레벨씩 내려가며 두 트리의 노드 값들을 비교하고, 한쪽의 값 목록이 다른 쪽과 정순서 혹은 역순서 중 하나로 일치하는지 확인하는 것이 핵심 아이디어입니다. 구체적인 알고리즘은 다음과 같습니다.
- root0과 root1을 각각 담고 있는 큐 que1, que2를 초기화합니다.
- 두 큐가 모두 비어 있지 않은 동안 아래 과정을 반복합니다.
- 현재 레벨 값을 저장할 values1, values2와 다음 레벨 노드를 저장할 temp1, temp2를 새로 생성합니다.
- que1과 que2에 담긴 요소 개수가 다르면 False를 반환합니다.
- i를 0부터 que1의 크기 − 1까지 반복하며, que1[i]와 que2[i]의 값을 각각 values1, values2에 추가합니다.
- que1[i]의 오른쪽 자식이 존재하면 temp1 끝에, 왼쪽 자식이 존재하면 temp1 끝에 추가합니다.
- que2[i]의 오른쪽 자식이 존재하면 temp2 끝에, 왼쪽 자식이 존재하면 temp2 끝에 추가합니다.
- values1이 values2와 다르면, values2를 뒤집은 목록(values2[::-1])과 한 번 더 비교합니다. 이마저 일치하지 않으면 False를 반환합니다.
- que1 := temp1, que2 := temp2로 갱신한 뒤 다음 레벨로 진행합니다.
- 모든 레벨 검사를 통과하면 True를 반환합니다.
아래 구현 예제를 통해 더 자세히 살펴보겠습니다.
구현 예제
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root0, root1):
que1 = [root0]
que2 = [root1]
while que1 and que2:
if len(que1) != len(que2):
return False
temp1 = []
temp2 = []
values1 = []
values2 = []
for i in range(len(que1)):
values1.append(que1[i].val)
values2.append(que2[i].val)
if que1[i].right:
temp1.append(que1[i].right)
if que1[i].left:
temp1.append(que1[i].left)
if que2[i].right:
temp2.append(que2[i].right)
if que2[i].left:
temp2.append(que2[i].left)
if values1 != values2:
if values1 != values2[::-1]:
return False
que1 = temp1
que2 = temp2
return True
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
print(ob.solve(root, root1))입력
root = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(3) root.right.right = TreeNode(5) root1 = TreeNode(2) root1.left = TreeNode(4) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5)
출력
True
동작 원리 정리
위 코드는 각 레벨마다 두 트리의 노드 값을 추출해 비교합니다. 첫 번째 트리에서는 노드 2의 오른쪽에 4가 위치하지만, 두 번째 트리에서는 왼쪽에 4가 있습니다. 이때 값 목록 [4]와 [4]는 순서에 관계없이 일치하므로 해당 레벨은 통과하고, 그다음 레벨에서도 동일한 방식으로 검사가 진행됩니다. 모든 레벨에서 좌우 교환으로 도달 가능한 배치인지 확인되면 최종적으로 True를 반환합니다.
이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 큐와 값 목록 저장에 필요한 공간 복잡도 역시 O(n)입니다.