Hex.*

LC662 - Maximum Width of Binary Tree

Posted on In
Datastructure and Algorithm: DAY 88. Leetcode: 283/2752

Description

Given the root of a binary tree, return 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 rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

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

Example 1:

1
2
3
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

1
2
3
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

1
2
3
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

Constraints:

1
2
The number of nodes in the tree is in the range [1, 3000].
-100 <= Node.val <= 100

Soution

Using the full binary tree number, the distance between any two nodes in the same layer (with empty nodes) can be easily calculated, and our BFS returns the layer with the largest distance between the leftmost and the rightmost.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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:
        ans = 0
        queue = deque([(1, root)])

        while queue:
            l, r = float('inf'), 0
            for _ in range(len(queue)):
                idx, popnode = queue.popleft()
                if popnode.left:
                    queue.append((idx*2, popnode.left))
                if popnode.right:
                    queue.append((idx*2+1, popnode.right))
                l, r = min(idx, l), max(idx, r)
            ans = max(ans, r-l+1)
        return ans

#Runtime: 42 ms, faster than 97.03% of Python3 online submissions for Maximum Width of Binary Tree.
#Memory Usage: 14.8 MB, less than 46.14% of Python3 online submissions for Maximum Width of Binary Tree.