이진 트리의 루트 노드가 주어졌을 때, 각 노드는 0부터 25까지의 값을 가지며 이 값들은 알파벳 소문자 'a'부터 'z'에 대응됩니다. 즉, 값 0은 'a', 값 1은 'b'와 같은 식으로 매핑됩니다. 우리가 찾아야 하는 것은 트리의 리프(leaf) 노드에서 시작하여 루트에서 끝나는 문자열 중 사전순(lexicographically)으로 가장 작은 문자열입니다.
예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.
이 경우 루트까지의 경로는 [0, 3, 25]이며, 이를 역순으로 읽으면 'a', 'd', 'z'가 되므로 출력 결과는 "adz"입니다.
문제 해결 접근 방식
이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 루트에서 리프까지 경로를 따라 내려가면서 방문한 노드의 문자를 누적하고, 리프에 도달하는 순간 지금까지 쌓인 경로를 역순으로 만들어 정답과 비교하는 것입니다.
알고리즘 단계
DFS 순회 메서드를 다음과 같이 정의합니다.
노드가 null이 아니라면,
노드의 값을 해당하는 문자로 변환하여 배열 A에 추가합니다.
노드에 왼쪽과 오른쪽 자식이 모두 없다면(즉, 리프 노드라면),
배열 A의 요소들을 역순으로 연결한 문자열과 현재 정답(ans)을 비교하여 더 작은 값을 ans에 저장합니다.
배열 A에서 마지막 요소를 제거합니다.
함수를 종료하고 반환합니다.
왼쪽 자식 노드로 dfs(node.left, A)를 재귀 호출합니다.
오른쪽 자식 노드로 dfs(node.right, A)를 재귀 호출합니다.
재귀 호출이 끝나면 배열 A에서 마지막 요소를 제거합니다(백트래킹).
반환합니다.
실제 메서드는 다음과 같이 동작합니다.
ans := "~" 로 초기화합니다. ('~'의 ASCII 코드는 소문자보다 크므로 초기 비교 기준으로 사용하기 좋습니다.)
dfs(root, 빈 배열 A)를 호출합니다.
ans를 반환합니다.
구현 예제
다음 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
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(object):
def smallestFromLeaf(self, root):
self.ans = "~"
self.dfs(root,[])
return self.ans
def dfs(self, node, A):
if node:
A.append(chr(node.data + ord('a')))
if not node.left and not node.right:
self.ans = min(self.ans, ''.join(reversed(A)))
A.pop()
return
self.dfs(node.left,A)
self.dfs(node.right,A)
A.pop()
return
root = make_tree([25,1,3,1,3,0,2])
ob = Solution()
print(ob.smallestFromLeaf(root))입력
[25,1,3,1,3,0,2]
출력
adz
정리
이 문제의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)입니다. 단, 각 리프마다 경로 문자열을 생성하고 비교하는 비용이 추가되므로 실질적으로 O(N × H) 수준이라고 볼 수 있습니다(H는 트리의 높이). 공간 복잡도는 재귀 호출 스택과 경로 저장용 배열 때문에 O(H)입니다.
핵심 포인트는 두 가지입니다. 첫째, 문자열이 리프 → 루트 방향으로 만들어지므로 리프에서 도달했을 때 배열을 뒤집어야 한다는 점, 둘째, 초기 정답을 '~'처럼 충분히 큰 문자로 설정해 첫 번째 결과와의 비교가 항상 올바르게 동작하도록 하는 점입니다. 백트래킹으로 배열을 원상복구하는 것도 잊지 마세요.