Maximum Width of Binary Tree LeetCode solution in Python

1
# Runtime: 46 ms (Top 93.81%) | Memory: 14.7 MB (Top 75.82%)
2
# Definition for a binary tree node.
3
# class TreeNode:
4
# def __init__(self, val=0, left=None, right=None):
5
# self.val = val
6
# self.left = left
7
# self.right = right
8
class Solution:
9
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
10
        q = deque([(root, 0)])
11
        res = 0
12

13
        while q:
14
            res = max(res, q[-1][1] - q[0][1] + 1)
15
            for _ in range(len(q)):
16
                curr, pos = q.popleft()
17

18
                if curr.left:
19
                    q.append((curr.left, pos * 2))
20
                if curr.right:
21
                    q.append((curr.right, pos * 2 + 1))
22

23
        return res