문제 개요
이진 트리가 하나 주어졌을 때, 전위 순회(preorder traversal) 방식으로 트리를 탐색하며 괄호와 정수로만 구성된 문자열을 생성해야 합니다. 이때 null 노드는 빈 괄호 쌍 “()”으로 표현하지만, 문자열과 원본 이진 트리 사이의 일대일 대응 관계에 영향을 주지 않는 빈 괄호 쌍은 모두 생략해야 합니다.
예를 들어 다음과 같은 트리가 입력으로 주어지면
출력은 5(6()(8))(7)이 됩니다.
결과가 이렇게 나오는 이유를 살펴보겠습니다. 루트 5의 왼쪽 자식은 6, 오른쪽 자식은 7입니다. 노드 6은 오른쪽 자식으로 8을 가지지만 왼쪽 자식이 없는데, 이 경우 왼쪽 자리에 빈 괄호 “()”을 남겨 두어야 8이 왼쪽이 아닌 오른쪽 자식임을 구분할 수 있습니다. 반면 노드 7은 자식이 없는 리프 노드이므로 그 하위의 빈 괄호는 생략되어 “(7)”로만 표현됩니다.
풀이 접근 방법
이 문제는 재귀 호출로 깔끔하게 해결할 수 있습니다. 단계별 절차는 다음과 같습니다.
- 결과를 담을 빈 문자열 ans를 준비합니다.
- 노드와 문자열을 인자로 받는 재귀 함수 pot()를 정의합니다.
- 노드가 null이면 빈 문자열을 반환합니다.
- 왼쪽과 오른쪽 자식이 모두 null인 리프 노드라면 노드 값을 문자열로 변환해 반환합니다.
- 그 외의 경우에는 결과 문자열 ss를 노드 값으로 초기화합니다.
- 왼쪽 자식이 존재하면 ss에 ‘(’ + 왼쪽 서브트리 결과 + ‘)’를 이어 붙이고, 존재하지 않으면 “()”를 붙입니다.
- 오른쪽 자식이 존재하면 ss에 ‘(’ + 오른쪽 서브트리 결과 + ‘)’를 이어 붙입니다. 오른쪽 자식이 없다면 아무것도 추가하지 않습니다.
- 완성된 ss를 반환합니다.
- 메인 함수에서는 루트 노드를 인자로 pot()를 호출한 결과를 최종 반환합니다.
여기서 핵심 규칙을 정리하면 다음과 같습니다.
- 오른쪽 자식은 있는데 왼쪽 자식이 없다면, 왼쪽 자리에 “()”을 반드시 남겨 트리 구조를 보존합니다.
- 오른쪽 자식이 없다면 해당 위치의 괄호를 생략해도 일대일 대응에는 문제가 없습니다.
구현 예제
아래 코드는 위 알고리즘을 파이썬으로 구현한 전체 예제입니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while len(que):
temp = que[0]
que.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution:
def tree2str(self, t: TreeNode):
ans = ''
def pot(node, s):
if node is None or node.data == 0:
return ''
if node.left is None and node.right is None:
return str(node.data)
ss = str(node.data)
if node.left is not None:
ss = ss + '(' + pot(node.left, '') + ')'
else:
ss = ss + '()'
if node.right is not None:
ss = ss + '(' + pot(node.right, '') + ')'
return ss
return pot(t, '')
ob = Solution()
root = make_tree([5, 6, 7, None, 8])
print(ob.tree2str(root))
입력
[5,6,7,None,8]
출력
5(6()(8))(7)
복잡도 분석 및 마무리
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로, 노드 수를 N이라 할 때 시간 복잡도는 O(N)입니다. 재귀 호출의 깊이는 트리의 높이에 비례하므로, 편향된 트리의 최악의 경우 공간 복잡도 역시 O(N)이 됩니다.
핵심은 왼쪽 자식이 없을 때만 “()”을 유지하고, 오른쪽 자식이 없을 때는 괄호를 생략한다는 점입니다. 이 규칙만 기억하면 어떤 형태의 이진 트리든 유일한 문자열 표현으로 변환할 수 있습니다. LeetCode의 “Construct String from Binary Tree”(606번) 문제와 동일한 유형이므로, 코딩 테스트 대비 연습용으로도 활용하기 좋습니다.