题目描述
思路解析动画文字版
难点就在空位。第 3 层有 5、3、9 三个节点，但它们不是一路挨着的——3 和 9 中间空了一格。怎么把这个「空隙」量出来、算进宽度里？
妙处在这：哪怕中间有空缺，座位号照样连续递增。一层最右节点的编号减最左节点的编号，再加 1，正好就是这层的宽度——空位自动被算进去了。
每层进队列时，第一个出队的就是最左、最后一个出队的就是最右。它俩的编号一减一加，就是这层宽度。下面用 [1,3,2,5,3,null,9] 这棵树一帧一帧地走。
这棵树 · 准备 BFS：这是例子树。注意第 3 层：5 在最左、9 在最右，中间空了位置。我们给每个节点编号（根=0，左孩子=2i，右孩子=2i+1），用 BFS 逐层算宽度。一帧一个动作，盯住右边面板里的编号。
根入队 · 编号 0：先把根 1 放进队列，给它编号 0。蓝色表示「已在队列、等待处理」。BFS 的规矩是一层处理完再下一层。
第1层 · 取出最左(也是最右)：处理第 1 层。这层只有根 1。它第一个出队，所以记下本层 first（最左编号）= 0。橙色的 1 是正在处理的节点 cur。
把孩子带编号入队：1 把两个孩子带编号塞进队列：左孩子 3 编号 2i=0，右孩子 2 编号 2i+1=1。它俩变蓝（已入队）。1 也是本层最后一个，所以 last 编号 = 0。
第1层算宽度 · last−first+1：第 1 层处理完。宽度 = last − first + 1 = 0 − 0 + 1 = 1。更新 ans = 1。根 1 变绿表示这层结清了。继续往下走。
第2层 · 取最左 3·0：进入第 2 层。第一个出队的是 3，编号 0——它是本层最左，记下 first = 0。橙色 cur 标着正在处理它。
3 把孩子带编号入队：节点 3 把它的两个孩子带编号入队：左孩子 5 编号 2×0=0，右孩子 3 编号 2×0+1=1。它俩变蓝（已入队）。本层 first 早已锁定 0。继续取本层下一个。
第2层 · 取最右 2·1：本层下一个出队的是 2，编号 1。它是本层最后一个，所以记下 last = 1。3 已处理完变绿，橙色 cur 移到 2。
2 把孩子带编号入队：节点 2 只有一个右孩子 9，编号 2×1+1=3；它的左孩子是空的，那个编号 2 的座位天生没人坐。但编号不跳号——9 照样拿到它该有的编号 3。现在第 3 层的队列是 5·0、3·1、9·3。
第2层算宽度 · 1−0+1：第 2 层结清：宽度 = last − first + 1 = 1 − 0 + 1 = 2。ans 更新到 2。3、2 都变绿。下面是关键的第 3 层——它有三个节点 5、3、9，中间还夹着一个空位。
第3层 · 取最左 5·0：进入第 3 层，队列里是 5·0、3·1、9·3 三个节点。第一个出队的是 5，编号 0，锁定 first = 0。它是本层最左，靠的就是这个最小的编号。
第3层 · 取中间 3·1：本层第二个出队的是中间这个节点 3，编号 1。5 处理完变绿，橙色 cur 移到 3。它俩都是叶子、没孩子入队。first 仍是 0，本层还剩最右的 9 没取，继续。
第3层 · 取最右 9·3：本层最后一个出队是 9，编号 3，记下 last = 3。注意编号：5 是 0、中间的 3 是 1、9 是 3——9 和 3 之间空了编号 2 那个座位（节点 2 的左孩子是空的），但编号不跳号。5、3 变绿，橙色 cur 到 9。
第3层算宽度 · 3−0+1：本层 first=0（最左的 5）、last=3（最右的 9），宽度 = last − first + 1 = 3 − 0 + 1 = 4！绿色框出最左 5、蓝色框出最右 9。ans 更新到 4。注意：5、3、9 三个节点编号是 0、1、3，中间编号 2 那个空位被这个差值自动算进去了——这正是宽度 4 的来历。
为何空位也算进宽度：把第 3 层的座位号摆出来：5 是 0、中间的 3 是 1、9 是 3，而编号 2 那个座位是空的（节点 2 的左孩子缺席）。最左 0、最右 3，宽度 = 3 − 0 + 1 = 4——你看，中间那个空座位 2 被这个差值自动算进去了，根本不用你专门去数它。
编号相减 · 比数节点强在哪：看懂编号的灵魂：这一层数节点只有 5、3、9 三个，可宽度是 4。差出来的那个 1，正是中间编号 2 的空座位。最右编号减最左编号加 1，空位被自动算进去了——这就是「编号相减」比「数节点个数」强的地方：跨度看的是座位号，不是有没有人坐。
本例最终 · ans = 4：本例 [1,3,2,5,3,null,9] 三层宽度分别 1、2、4，最大宽度 = 4，出在第 3 层。算法核心已演完：每层最右编号 − 最左编号 + 1，取最大。所有节点变绿，BFS 结束。
深树时编号是 2 的指数级，几十层就超过 int 范围。所以 Java 要用 long，或者每层把编号「归零平移」（减去本层第一个编号）防溢出。下一帧讲归零技巧。
防溢出 · 每层编号归零：防溢出小技巧：每处理一层，把这层所有编号都减去本层第一个编号 first，让本层编号从 0 重新开始。差值（宽度）不受影响，但编号不会一直翻倍变大。紫色标出被归零平移的两端。
一句话记住它：别去数节点个数，去看座位号的跨度。最右座位号减最左座位号加 1，中间空着的座位也算在宽度里，这正是题目要的。
易错实演 · 数节点个数错：看这个错法：第 3 层数到 5、3、9 三个节点，就以为宽度是 3。错——这漏掉了它们之间的空位。正确永远看编号跨度：最右编号减最左编号加 1，空位自动计入。
易错实演 · 编号写反：另一个坑：把左右孩子的编号公式写反。左孩子必须是 2i、右孩子必须是 2i+1，写反了同层节点的座位号全乱，宽度自然算错。记牢这个标准编号方向。
三个边界：空树返回 0；单节点宽度 1；又深又偏的树要警惕编号溢出，靠 long 或每层归零兜住。
面试常追问三点：编号为什么能算空位、怎么防溢出、能不能 DFS。把「编号 = 满树座位号、宽度 = 编号跨度」这条主线讲清就稳了。
参考代码
from collections import deque# 树节点 left/right/val，Python 无需另外定义class Solution: def widthOfBinaryTree(self, root): if not root: return 0 ans = 0 q = deque([(root, 0)]) # (节点, 编号) while q: sz = len(q) first = q[0][1] # 本层最左编号 last = first for _ in range(sz): node, idx = q.popleft() last = idx # 不断更新到最右 if node.left: q.append((node.left, 2 * idx)) # 左=2i if node.right: q.append((node.right, 2 * idx + 1)) # 右=2i+1 ans = max(ans, last - first + 1) # 本层宽度 return ans复杂度
- 时间复杂度：O(n)，BFS 每个节点恰好入队、出队各一次，n 是节点总数。
- 空间复杂度：O(n)，队列最多存某一层的全部节点，最宽一层约 n/2，量级 O(n)。
- 编号防溢出：long / 归零，编号按 2i 指数增长，需 long 或每层减 first 归零，否则深树会溢出。
易错点
面试追问把动画讲成自己的话
追问为什么给节点编号能算出含空位的宽度？
追问编号为什么会溢出，怎么防？
追问能不能用 DFS 解？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树中的最大路径和
LeetCode 124 · 困难 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题