662. Maximum Width of Binary Tree

https://leetcode.com/problems/maximum-width-of-binary-tree/

Maximum Width of Binary Tree - LeetCode

트리를 이용한 문제이며 트리의 전위순회, 후위순외같은 개념은 흔하지만 level order를 활용한 문제는 흔하지 않아서 생각하는데 약간 시간이 걸렸을 수도 있다.

또한 Tree의 node마다 값이 주어지는데 가장 넓은 넓이를 가진 층을 찾기 위해서는 각 node들의 값은 쓸모가 없다.

풀이 방법은 다음과 같다.

* 각 층마다의 Node의 위치 값을 계산 (왼쪽노드 : 부모노드 * 2, 오른쪽노드 : 부모노드 * 2 + 1)

* deque를 이용하여 Node의 위치값들을 dictionary에 층마다 정리해서 넣기

* 층마다 최대값과 최소값을 구해서 최대값 - 최소값으로 길이를 구하기

* 전체 최대값 구하기

 

from collections import defaultdict, deque

def level_order(root, level, level_dict):
    
    q = deque()
    q.append((root, level, 1))

    while q:
        
        now, depth, num = q.popleft()

        if not level_dict[depth]:
            level_dict[depth] = []

        level_dict[depth].append(num)
        
        # left append
        if now.left:
            q.append((now.left, depth+1, num*2))
        
        # right append
        if now.right:
            q.append((now.right, depth+1, num*2 + 1))

    return level_dict

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

        level_dict = defaultdict(list)
        result_dict = level_order(root, 0, level_dict)

        max_length = -1
        for key in result_dict.keys():

            max_value = max(result_dict[key])
            min_value = min(result_dict[key])

            max_length = max(max_length, (max_value - min_value + 1))

        return max_length