LC 0662 [M] Maximum Width of Binary Tree - ALawliet/algorithms GitHub Wiki
We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2i and 2i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width is end[level] - start[level] + 1. Then, we just need to find the maximum width.
# 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
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
max_width = 0
Q = deque([ (root, 1) ]) # node, i (index of this node if this binary tree were represented as an array so it includes nulls)
while Q:
end_level = Q[-1][1]
start_level = Q[0][1]
width_level = end_level - start_level + 1
max_width = max(max_width, width_level)
for _ in range(len(Q)):
node, i = Q.popleft()
# print(node.val, i)
if node.left:
Q.append( (node.left, 2*i) )
if node.right:
Q.append( (node.right, 2*i + 1) )
return max_width