문제 개요
이진 트리(binary tree)가 주어졌을 때, 가장 깊은 레벨에 있는 노드의 값을 찾아야 합니다. 만약 가장 깊은 레벨에 노드가 두 개 이상 존재한다면, 그중 가장 왼쪽에 있는 노드의 값을 반환해야 합니다.
예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.
이 경우 노드 4와 7이 모두 가장 깊은 레벨에 있지만, 4가 더 왼쪽에 위치하므로 출력 결과는 4가 됩니다.
접근 방법: 레벨 순회(BFS)
이 문제는 너비 우선 탐색(BFS), 즉 레벨 순회 방식으로 해결할 수 있습니다. 각 레벨을 순회할 때마다 해당 레벨의 첫 번째 노드 값을 기록하면, 순회가 끝났을 때 마지막으로 기록된 값이 곧 가장 깊은 레벨의 가장 왼쪽 노드 값이 됩니다.
알고리즘 단계
- 루트 노드 하나를 담은 큐(queue)를 생성합니다.
left_max변수를 루트 노드의 값으로 초기화합니다.- 큐가 비어 있지 않은 동안 다음을 반복합니다.
- 현재 큐의 크기를
level_size로 저장합니다. 이 값이 현재 레벨의 노드 개수입니다. level_size만큼 반복하면서 큐에서 노드를 하나씩 꺼냅니다.- 각 레벨의 첫 번째 노드(i == 0)라면
left_max를 해당 노드의 값으로 갱신합니다. - 꺼낸 노드의 왼쪽 자식이 존재하면 큐에 추가하고, 오른쪽 자식이 존재해도 큐에 추가합니다.
- 현재 큐의 크기를
- 모든 순회가 끝나면
left_max를 반환합니다. 이 값이 가장 깊은 레벨의 가장 왼쪽 노드 값입니다.
BFS는 레벨 단위로 트리를 탐색하기 때문에, 마지막 레벨의 첫 번째 노드가 자연스럽게 '가장 깊으면서 가장 왼쪽'인 노드가 된다는 점을 활용한 아주 효율적인 방법입니다.
구현 코드
다음은 위 알고리즘을 Python으로 구현한 예제입니다.
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class Solution:
def solve(self, root):
queue = [root]
left_max = root.val
while len(queue) > 0:
level_size = len(queue)
for i in range(level_size):
temp = queue.pop(0)
if i == 0:
left_max = temp.val
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
return left_max
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))입력 예시
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
출력 결과
4
복잡도 분석
- 시간 복잡도: O(n) — 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(w) — w는 트리의 최대 폭(width)으로, 큐에 저장되는 노드 수에 비례합니다.
참고로 성능을 더 개선하려면 queue.pop(0)(O(n) 연산) 대신 collections.deque를 사용하여 popleft()로 O(1) 시간에 요소를 꺼내는 것이 좋습니다.