[리트코드] 662. 이진트리의 최대 너비

# 문제 설명

이진트리의 root가 주어질 때, 주어진 트리의 최대 너비를 반환해라. 여기서 최대 너비란 모든 level들 중에 최대로 하는 너비를 말한다.

한 level의 너비는 그 끝의 노드들 간의 길이로 정의한다. 노드들 사이의 null 노드들도 또한 길이 계산에 포함한다.

 

# 입출력 예시

입력	출력
[1,3,2,5,3,null,9]	4
[1,3,null,5,3]	2
[1,3,2,5]	2

 

# 코드 풀이 1.  queue를 이용하여 index 계산

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        answer = 0
        q = deque([(0, root)]) # index, node
        while q:
            n = len(q)
            idxs = []
            for _ in range(n):
                index, node = q.popleft()
                idxs.append(index)
                if node.left:
                    q.append((index*2+1, node.left))
                if node.right:
                    q.append((index*2+2, node.right))
            answer = max(answer, max(idxs)-min(idxs)+1)
        return answer

 

# 코드 풀이 2.  재귀를 이용하여 index 계산

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import defaultdict
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        depths = defaultdict(list) # level: index
        def dfs(node, level, index):
            if node:
                depths[level].append(index)
                dfs(node.left, level+1, index*2)
                dfs(node.right, level+1, index*2+1)
        dfs(root, 0, 0)
        return max([max(depths[level]) - min(depths[level]) + 1  for level in depths])

 

# 핵심 포인트

• 한 level의 너비를 계산하기 위해, 각 level에서의 노드들의 index를 저장한다.
• index를 0부터 세면, 왼쪽 노드의 경우 항상 2의 배수고 오른쪽 노드는 그보다 항상 1이 크다.

 

참고 자료.