Maximum Width of Binary Tree
LeetCode 662 二叉树最大宽度：层序遍历 + 下标编号，注意每层归一化防溢出。
#resource / algorithm
#type / howto
#status / evergreen
#ds / tree
#algo / bfs
#source / leetcode
[!info] related notes 算法面试题型 MOC 二叉树高频题
Maximum Width of Binary Tree
LeetCode: https://leetcode.cn/problems/maximum-width-of-binary-tree/
思路（BFS + 编号）
给每个节点一个“完全二叉树下标”编号：
- 根节点 index = 1
- 左孩子 =
2 * index - 右孩子 =
2 * index + 1
每一层的宽度 = lastIndex - firstIndex + 1。
注意：直接用全局下标可能溢出，所以每层都做一次归一化：
base = 本层第一个节点的 index- 本层所有 index 都用
index - base来计算并生成下一层的 index
Java Template
import java.util.*;
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
Queue<Long> idx = new LinkedList<>();
q.add(root);
idx.add(1L);
int ans = 1;
while (!q.isEmpty()) {
int size = q.size();
long base = idx.peek();
long first = 0, last = 0;
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
long id = idx.poll() - base;
if (i == 0) first = id;
if (i == size - 1) last = id;
if (cur.left != null) {
q.add(cur.left);
idx.add(id * 2);
}
if (cur.right != null) {
q.add(cur.right);
idx.add(id * 2 + 1);
}
}
ans = Math.max(ans, (int) (last - first + 1));
}
return ans;
}
}