두 개의 이진 트리(binary tree)가 주어졌을 때, 첫 번째 트리의 각 레벨이 두 번째 트리의 같은 레벨과 아나그램(anagram) 관계인지 확인하는 문제를 살펴보겠습니다. 여기서 아나그램이란 구성 요소는 같지만 순서만 다른 경우를 의미합니다. 모든 레벨이 아나그램이라면 True를, 하나라도 다르면 False를 반환하면 됩니다.
예를 들어 다음과 같은 두 트리가 입력으로 주어진다면,
출력 결과는 True가 됩니다.
문제 해결 접근 방식
이 문제는 레벨 순회(level order traversal)와 큐(queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 트리를 동시에 레벨 단위로 탐색하면서, 각 레벨의 노드 값들을 정렬한 뒤 서로 일치하는지 비교하는 것입니다.
알고리즘 단계
tree_1은 첫 번째 트리의 루트 노드,tree_2는 두 번째 트리의 루트 노드입니다.- 두 트리가 모두
null(빈 트리)이면True를 반환합니다. - 둘 중 하나만
null이면 구조가 다르므로False를 반환합니다. - 두 개의 큐
queue1,queue2를 생성하고 각각 루트 노드를 삽입합니다. - 반복문 안에서 다음을 수행합니다:
- 각 큐의 현재 크기(
size1,size2)를 확인합니다. - 크기가 다르면 해당 레벨의 노드 수가 다른 것이므로
False를 반환합니다. - 크기가 0이면 모든 레벨 탐색이 끝난 것이므로 반복을 종료합니다.
- 현재 레벨의 노드 값을 저장할 리스트
curr_level1,curr_level2를 생성합니다. - 큐에서 노드를 하나씩 꺼내며 자식 노드를 큐에 추가하고, 노드 값을 현재 레벨 리스트에 기록합니다.
- 한 레벨의 순회가 끝나면 두 리스트를 각각 정렬한 후 비교합니다.
- 정렬된 두 리스트가 다르면
False를 반환합니다.
- 각 큐의 현재 크기(
- 모든 레벨이 일치하면 최종적으로
True를 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
def make_tree(elements):
tree = tree_node(elements[0])
for element in elements[1:]:
insert_value(tree, element)
return tree
def insert_value(temp, value):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if value is not None:
temp.left = tree_node(value)
else:
temp.left = tree_node(0)
break
else:
que.append(temp.left)
if (not temp.right):
if value is not None:
temp.right = tree_node(value)
else:
temp.right = tree_node(0)
break
else:
que.append(temp.right)
class tree_node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def solve(tree_1, tree_2):
if (tree_1 == None and tree_2 == None):
return True
if (tree_1 == None or tree_2 == None):
return False
queue1 = []
queue2 = []
queue1.append(tree_1)
queue2.append(tree_2)
while (1):
size1 = len(queue1)
size2 = len(queue2)
if (size1 != size2):
return False
if (size1 == 0):
break
curr_level1 = []
curr_level2 = []
while (size1 > 0):
node1 = queue1[0]
queue1.pop(0)
if (node1.left != None):
queue1.append(node1.left)
if (node1.right != None):
queue1.append(node1.right)
size1 -= 1
node2 = queue2[0]
queue2.pop(0)
if (node2.left != None):
queue2.append(node2.left)
if (node2.right != None):
queue2.append(node2.right)
curr_level1.append(node1.value)
curr_level2.append(node2.value)
curr_level1.sort()
curr_level2.sort()
if (curr_level1 != curr_level2):
return False
return True
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))입력
[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]
출력
True
코드 설명 및 시간 복잡도
make_tree 함수는 리스트 값을 순서대로 트리에 삽입하여 이진 트리를 생성하고, solve 함수는 앞서 설명한 알고리즘대로 두 트리를 레벨 단위로 비교합니다. 위 예제에서 첫 번째 트리의 루트 자식들은 [6, 7], 두 번째 트리의 루트 자식들은 [7, 6]으로 정렬하면 동일하므로 아나그램 관계입니다. 그 아래 레벨도 마찬가지로 [9, 8]과 [8, 9]로 일치하기 때문에 최종 결과는 True입니다.
시간 복잡도는 각 노드를 한 번씩 방문하고 레벨별 정렬이 수행되므로 O(n log n)입니다. 여기서 n은 트리의 전체 노드 수입니다. 공간 복잡도는 큐와 레벨 리스트 저장에 O(n)이 필요합니다.