- Problem

662. Maximum Width of Binary Tree

- DFS 풀이

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        levels = defaultdict(list)

        def dfs(node, level, idx):
            if not node:
                return
            
            levels[level].append(idx)

            dfs(node.left, level + 1, idx * 2)
            dfs(node.right, level + 1, idx * 2 + 1)
        
        dfs(root, 0, 0)
        max_width = 1

        for i, v in levels.items():
            max_width = max(max_width, v[-1] - v[0] + 1)

        return max_width

- 결과

- BFS 풀이

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:        
        q = deque([(root, 1)])
        max_width = 0
        
        while q:
            _, head_idx = q[0]
            for _ in range(len(q)):
                node, tail_idx = q.popleft()
                if node.left:
                    q.append((node.left, tail_idx * 2))
                if node.right:
                    q.append((node.right, tail_idx * 2 + 1))
            
            max_width = max(max_width, tail_idx - head_idx + 1)
        
        return max_width

- 결과