LeetCode 662. 二叉树最大宽度
目录
题目描述
题意分析
给定二叉树的根节点，求所有层里最大的那个「宽度」。这题的全部难点都压在宽度的定义上：某一层的宽度不是这一层有几个节点，而是这一层最左端点与最右端点之间的位置差——把这棵树想象成一棵完全二叉树，两个端点之间缺失的
null位置也要计入宽度。例如某层只有最左、最右两个真实节点、中间隔着 3 个空位，宽度是 5 而不是 2。换句话说，答案由「位置」决定而不是由「个数」决定，任何只数节点数量的做法从定义上就是错的。
约束是节点数最多 3000，题目保证答案在 32 位整数范围内。但要注意：节点数不大不代表位置编号不大——一棵 3000 个节点的树可以深达 3000 层，节点在完全二叉树中的编号随深度指数增长，中间过程可能远远超出 64 位整数，这是本题第二个必须处理的信号。边界上，题目保证至少有一个节点，单节点树宽度为 1。
解法：层序遍历记录位置编号
核心思路
问题关键：宽度包含两端节点之间的空位，不能直接用本层真实节点数。真正需要的是每个节点在一棵完全二叉树中的位置。
为什么选 BFS + 编号：BFS 能一次拿到一整层；给节点使用堆式编号
i，其左右孩子编号为2i + 1、2i + 2，那么本层宽度就是right - left + 1。只保存真实节点及编号，就能计算空位，无需真的补null。不变量：处理每一层时，队列前
size个节点按从左到右排列，携带的编号保持它们的相对位置。因此最右编号减最左编号再加 1，必然等于该层定义中的宽度。原始编号会随深度指数增长。每层先把所有编号减去本层最左编号，再生成孩子编号；整体平移不改变编号差，却能避免无意义的溢出。
解题步骤
- 空树返回
0；否则将根节点和编号0同步入队。- 每轮记录当前层节点数
size，并取队首编号作为归一化基准levelStart。- 弹出本层
size个节点，将编号减去levelStart；左右孩子非空时，按2i + 1、2i + 2携带新编号入队。- BFS 保证层内从左到右处理，所以最后一次得到的归一化编号就是最右位置；用
lastIndex + 1更新答案。例如
[1,3,2,5,3,null,9]的第三层编号可归一化为0、1、3，虽然只有 3 个真实节点，宽度仍是3 - 0 + 1 = 4。
代码实现
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)$，每个真实节点入队、出队各一次。
- 空间复杂度：$O(w)$，
w是树的最大层宽；最坏为 $O(n)$。
关键点总结
- 面试开场先强调：题目求的是两端的位置差，不是节点个数。
- 堆式编号保留空位信息，BFS 负责按层结算宽度。
- 同层编号整体减去最左编号不改变宽度，并能抑制编号增长。
- 节点与编号必须严格同步入队、出队。
易错点总结
- 把
queue.size()当宽度会漏算空位：[1,3,2,5,null,null,9]的第三层宽度是4，不是2。- 宽度公式不能漏掉
+1；单节点树的宽度应为1。- 编号不归一化会在深树中溢出；Java 应使用
long，Go 使用uint64保存编号。- 0 起始编号必须配套
2i + 1、2i + 2，不要和 1 起始的2i、2i + 1混用。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 按层分组的 BFS 模板本身，本题的骨架来源 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 在层序模板上按层号交替反转输出方向 |
| 107. 二叉树的层序遍历 II | 中等 | 层序结果自底向上，考察结果的逆序组织 |
| 199. 二叉树的右视图 | 中等 | 只取每层最后一个节点，与本题「最右端点」同源 |
| 429. N 叉树的层序遍历 | 中等 | 层序模板从二叉推广到多叉孩子列表 |
| 513. 找树左下角的值 | 中等 | 定位最底层最左节点，关注端点而非整层 |
| 515. 在每个树行中找最大值 | 中等 | 层内聚合从「位置差」换成「最大值」 |
| 637. 二叉树的层平均值 | 简单 | 层内聚合为平均值，注意求和溢出 |
| 958. 二叉树的完全性检验 | 中等 | 同款堆式编号，用编号连续性判定完全性 |
| 1302. 层数最深叶子节点的和 | 中等 | 只对最后一层做聚合，识别最深层的时机 |
| LCR 044. 在每个树行中找最大值 | 中等 | 515 的镜像题，练同一模板的变式 |
| LCR 045. 找树左下角的值 | 中等 | 513 的镜像题，可用从右到左 BFS 简化 |
| LCR 046. 二叉树的右视图 | 中等 | 199 的镜像题，DFS 先右后左也可解 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 不分层的裸 BFS，输出一维序列 |
| 剑指 Offer 32 - II. 从上到下打印二叉树 II | 简单 | 分层输出二维结果，等价于 102 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 之字形打印，等价于 103 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层节点转成链表，层序结果的另一种载体 |