第 72 题
假设二叉树采用二叉链表存储结构，设计一个算法求非空二叉树 b 的宽度（结点数最多的一层的结点数）。
[tag_link]
参考答案
逐层 BFS。每轮先记录当前队列长度 levelSize，它就是本层宽度，再处理恰好 levelSize 个结点并将下一层孩子入队。
伪代码
Width(T):
if T == null: return 0
Q.enqueue(T); maxWidth = 0
while not Q.empty():
levelSize = Q.size()
maxWidth = max(maxWidth, levelSize)
repeat levelSize times:
p = Q.dequeue()
if p.left != null: Q.enqueue(p.left)
if p.right != null: Q.enqueue(p.right)
return maxWidth
复杂度
时间 O(n)；队列最多容纳一层及相邻层的部分结点，空间 O(w)，w 为最大宽度。
边界条件
空树返回 0；题设非空时结果至少为 1；不能把空指针计入层宽。
易错点
必须在本层出队前固定 levelSize；若边入队边读取变化后的队长，会把下一层结点混入本层。
评分要点
层序遍历；固定每层结点数；维护 maxWidth；处理空树；复杂度正确。