(LeetCode) Maximum Width of Binary Tree with Python

Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels.

: 이진 트리가 주어지면, 주어진 트리의 최대 너비를 얻는 함수를 작성한다. 트리의 최대 너비는 모든 수준 중에서 최대 너비이다.

 

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

: 한 수준의 너비는 끝 노드 사이의 길이로 정의된다. (수준에서 가장 왼쪽과 오른쪽에 있는 Null 이 아닌 노드에서 끝 노드 사이의 null 노드도 길이 계산에 포함된다.)

 

It is guaranteed that the answer will in the range of 32-bit signed integer.

: 답은 32비트 정수 범위에 있음을 보증한다.

 

Example 1:

Input:

         1
      ↙  ↘
     3       2
  ↙  ↘      ↘
5       3        9

Output: 4

Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

가장 큰 너비는 세 번째 레벨에 존재하는 5,3,null,9 이며, 길이는 4이다.

 

Example 2:

Input:

              1
           ↙
          3
       ↙   ↘
      5        3

Output: 2

Explanation: The maximum width existing in the third level with the length 2 (5,3).

가장 큰 너비는 세 번째 레벨에 존재하는 5,3 이며, 길이는 2이다.

 

Example 3:

Input:

             1
          ↙   ↘
         3       2
      ↙
    5

Output: 2

Explanation: The maximum width existing in the second level with the length 2 (3,2).

가장 큰 너비는 두 번째 레벨에 존재하는 3,2 이며, 길이는 2이다.

 

Example 4:

Input:

                         1
                      ↙   ↘
                     3        2
                  ↙            ↘
                5                  9
              ↙                     ↘  
            6                            7

Output: 8

Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

가장 큰 너비는 네 번째 레벨에 존재하는 6,null,null,null,null,null,null,7 이며, 길이는 8이다.

 

 

Constraints:

• The given binary tree will have between 1 and 3000 nodes.

 

💯 Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def widthOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """# root : 현재 노드 / 0 : 인덱스에서의 위치 값
        queue = [(root,0)]
        width_max = 0
        #print(queue)
 
        while queue:
            tmp = []
            # queue 안에 node와 pos를 반복
            for node, pos in queue:
                #print(node)
                #print(pos)
                # node의 왼쪽 값이 있다면
                if node.left:
                    # tmp에 append()를 통해서 (node.left, pos*2) 를 더한다.
                    tmp.append((node.left, pos*2))
                # node의 오른쪽 값이 있다면
                if node.right:
                    #tmp에 (node.right, pos*2+1)을 더한다.
                    tmp.append((node.right, pos*2 +1))
 
            #print(queue)
            # 너비를 구한다. (큰 값 - 작은 값)
            width = queue[-1][1] - queue[0][1] + 1
            #  width_max와 width 중에서 제일 큰 값을 width_max에 선언
            width_max = max(width_max, width)
        # width_max 제일 큰 너비 값을 반환한다.
        return width_max

 

 

📚 참고

www.daleseo.com/python-queue/

파이썬에서 큐(queue) 자료 구조 사용하기