LeetCode 662. 二叉树最大宽度
题目描述
题意分析
二叉树每一层的宽度，是在假想补齐空位后，这一层最左、最右非空节点之间的位置跨度，两个端点本身和中间缺失节点的位置都要计入。端点外侧的空位不计入宽度，返回所有层宽度的最大值。
因此，宽度不等于该层真实节点的数量，也不由节点值决定。即使某层只有少量节点，只要它们的位置相隔很远，宽度仍可能很大。题目保证最终答案在 32 位有符号整数范围内，但深层节点的绝对位置编号仍可能非常大。
解法：层序遍历记录位置编号
核心思路
[!blue]
给根节点编号
0，位置为i的节点，其左右孩子的位置分别记为2 * i + 1和2 * i + 2。即使某个孩子不存在，它对应的位置仍被编号规则保留下来。因此，同一层最右与最左节点的编号差再加一，就包含了两端之间的所有空位，不必真的把空节点放进队列。使用 BFS 按层处理，只将真实节点及其位置编号入队。父节点按从左到右的顺序出队，每个父节点又先加入左孩子、再加入右孩子，所以新一层的节点和编号也保持从左到右。每层开始时固定
size，只处理这size个节点，避免把新入队的下一层混入当前层。直接沿用绝对编号会随树深成倍增长，即使每层只有一个节点也可能溢出。为此，每层取最左编号
levelStart，把每个节点的编号统一减去它，得到本层的相对位置index。减去同一个数不改变差值，最左位置变为0，最后处理的lastIndex加一就是本层宽度。生成下一层编号时也使用相对位置。把父编号
i改为i - levelStart后，左右孩子的编号都相当于统一减去了2 * levelStart，所以它们之间的相对距离仍不变。这说明每一层都可以重复归一化，而不会丢失空位信息。归一化后的编号受当前层跨度约束，但乘二生成孩子时仍可能暂时超过 32 位整数，因此 Java 用
long，Go 用uint64保存编号。最终求出的宽度才按题目保证转换为返回类型。
解题步骤
- 空树返回
0；否则将根节点和编号0分别放入两个同步的队列。- 每层开始时记录当前节点数
size，取编号队列首项作为levelStart。- 连续取出
size对节点与编号，将编号减去levelStart，并更新lastIndex。- 按左、右顺序，将非空孩子及相对位置计算出的
2 * index + 1、2 * index + 2同步入队。- 本层结束后用
lastIndex + 1更新最大宽度；所有层处理完后返回答案。
代码实现
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> nodeQueue = new ArrayDeque<>();
Deque<Long> indexQueue = new ArrayDeque<>();
nodeQueue.offer(root);
indexQueue.offer(0L);
int ans = 0;
while (!nodeQueue.isEmpty()) {
int size = nodeQueue.size();
long levelStart = indexQueue.peekFirst();
long lastIndex = 0;
for (int i = 0; i < size; i++) {
TreeNode node = nodeQueue.poll();
long index = indexQueue.poll() - levelStart;
lastIndex = index;
// 编号归一化后再扩展孩子，避免深层编号过大。
if (node.left != null) {
nodeQueue.offer(node.left);
indexQueue.offer(index * 2 + 1);
}
if (node.right != null) {
nodeQueue.offer(node.right);
indexQueue.offer(index * 2 + 2);
}
}
ans = Math.max(ans, (int) (lastIndex + 1));
}
return ans;
}
}
func widthOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
nodes := []*TreeNode{
root,
}
indexes := []uint64{
0,
}
ans := 0
for len(nodes) > 0 {
size := len(nodes)
levelStart := indexes[0]
var lastIndex uint64
for i := 0; i < size; i++ {
node := nodes[0]
nodes = nodes[1:]
index := indexes[0] - levelStart
indexes = indexes[1:]
lastIndex = index
// 当前层编号先归一化，再生成下一层编号。
if node.Left != nil {
nodes = append(nodes, node.Left)
indexes = append(indexes, index*2+1)
}
if node.Right != nil {
nodes = append(nodes, node.Right)
indexes = append(indexes, index*2+2)
}
}
ans = maxInt(ans, int(lastIndex+1))
}
return ans
}
func maxInt(a int, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，
n为真实节点数。每个节点只入队、出队各一次，编号运算为常数时间。- 空间复杂度：$O(w)$，
w为单层真实节点数量的最大值。队列可能同时保留当前层尾部与下一层前部，但仍是 $O(w)$；这里的w不包含不存在的节点位置。
关键点总结
[!green]
- 位置编号保存间隔，队列只保存真实节点，两者职责不同。
- 一层统一平移不改变宽度，孩子编号也只发生统一平移，因此可以逐层归一化。
- 当前层大小提前固定，节点与编号严格同步出入队，才能正确取得左右端点。
易错点总结
[!yellow]
- 把队列长度当成宽度会漏掉端点之间的空位；宽度应按位置差计算。
- 宽度公式漏掉
+1，会让只有一个节点的层得到宽度0。- 处理一层时用不断变化的队列长度控制循环，会把下一层节点混进来。
- 只换成较宽的整数类型，却不做逐层归一化，仍无法阻止深树绝对编号持续增长。
- 节点入队后没有同步加入编号，或节点与编号弹出的顺序不同，会破坏位置对应关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 每层真实节点数不等于本题宽度，本题还计入两端之间缺失位置，需要保存位置编号。 |
| 958. 二叉树的完全性检验 | 中等 | 同样利用完全二叉树的位置编号理解空隙，原题判断是否缺位，本题计算最外两端的跨度。 |