이진 트리가 하나 주어졌을 때, 트리에서 가장 넓은 레벨의 최대 너비(maximum width)를 구하는 문제입니다. 여기서 레벨의 너비란 해당 레벨에서 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드 사이에 존재할 수 있는 노드의 개수를 의미합니다.
예를 들어 다음과 같은 이진 트리가 입력으로 주어지면,
출력 결과는 2가 됩니다.
해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)과 위치 번호 매기기(position indexing)를 활용하면 효율적으로 해결할 수 있습니다. 각 노드에 힙(heap) 구조처럼 위치 번호를 부여하는 방식으로, 어떤 노드의 위치가 pos라면 왼쪽 자식은 2*pos, 오른쪽 자식은 2*pos+1이 됩니다.
이를 위해 다음과 같은 단계를 따릅니다.
- 각 깊이별 최소 위치와 최대 위치를 저장할 맵(딕셔너리) d를 생성합니다. 최솟값은 무한대(infinity), 최댓값은 0으로 초기화합니다.
- dfs() 함수를 정의합니다. 이 함수는 루트 노드, 위치 pos(기본값 0), 깊이 depth(기본값 0)를 매개변수로 받습니다.
- 노드가 null이면 그대로 반환합니다.
- d[depth][0]에는 기존 값과 현재 pos 중 더 작은 값을 저장합니다.
- d[depth][1]에는 기존 값과 현재 pos 중 더 큰 값을 저장합니다.
- 왼쪽 자식에 대해 dfs(node.left, 2*pos, depth+1)를 재귀 호출합니다.
- 오른쪽 자식에 대해 dfs(node.right, 2*pos+1, depth+1)를 재귀 호출합니다.
메인 메소드에서는 아래와 같이 처리합니다.
- dfs(root)를 호출하여 전체 트리를 순회합니다.
- mx를 0으로 초기화합니다.
- d에 저장된 모든 (최소, 최대) 쌍에 대해 left와 right를 구하고, mx를 max(mx, right-left+1)로 갱신합니다.
- mx를 반환합니다.
구현 예제
from collections import defaultdict
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
d=defaultdict(lambda: [1e9,0])
def dfs(node, pos=0, depth=0):
if not node:
return
d[depth][0]=min(d[depth][0],pos)
d[depth][1]=max(d[depth][1],pos)
dfs(node.left,2*pos,depth+1)
dfs(node.right,2*pos+1,depth+1)
dfs(root)
mx=0
for interval in d.values():
l,r=interval
mx=max(mx,r-l+1)
return mx
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))
입력
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
출력
2
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(n) — 재귀 호출 스택과 깊이별 위치 정보를 저장하는 맵이 추가로 필요합니다.