二叉树最大宽度怎么求？为什么要给节点编号？

简化版

最大宽度按完全二叉树位置计算，包含两端非空节点之间的空位。BFS 时给节点编号，左孩子 2*i，右孩子 2*i+1，每层宽度等于最后编号减第一个编号加 1；每层归一化编号可避免溢出。

详细版

普通层序只知道每层有多少非空节点，但最大宽度要把中间空位算进去，所以需要位置编号。每层记录第一个节点编号 first，遍历该层时用相对编号 idx - first 入队孩子，当前层宽度用原始或相对的首尾编号计算。

int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    Queue<Pair<TreeNode, Long>> q = new ArrayDeque<>();
    q.offer(new Pair<>(root, 0L));
    long ans = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        long base = q.peek().getValue();
        long first = 0, last = 0;
        for (int i = 0; i < size; i++) {
            var pair = q.poll();
            TreeNode node = pair.getKey();
            long idx = pair.getValue() - base;
            if (i == 0) first = idx;
            if (i == size - 1) last = idx;
            if (node.left != null) q.offer(new Pair<>(node.left, idx * 2));
            if (node.right != null) q.offer(new Pair<>(node.right, idx * 2 + 1));
        }
        ans = Math.max(ans, last - first + 1);
    }
    return (int) ans;
}

如果只用队列长度，会漏算空洞，答案会偏小。

完整版教学

一、最大宽度不是每层非空节点数

这题的“宽度”按完全二叉树位置定义：一层中最左非空节点到最右非空节点之间的所有位置都算，包括中间空节点。普通 BFS 的队列长度只统计非空节点个数，无法表示空洞位置。

        1
       / \
      3   2
     /     \
    5       9

第三层非空节点数 = 2
第三层宽度 = 4, 位置为 [5,空,空,9]

这个例子说明为什么必须引入位置编号，而不是只看当前层队列大小。

更细一点看，BFS 队列里只会保存真实存在的节点，它天然会把不存在的空位压缩掉。可最大宽度题的定义偏偏要保留这种“视觉上的空位”，因为宽度描述的是这一层在完全二叉树坐标系中的跨度。也就是说，队列长度回答的是“这一层有几个真实节点”，编号差回答的是“这一层从最左到最右占了几个位置”。这两个问题不一样，答案自然也可能不一样。

二、编号来自堆式数组存储

完全二叉树可以用数组表示，若根编号为 0，则左孩子编号是 2*i，右孩子是 2*i+1；若根编号为 1，则左孩子是 2*i，右孩子是 2*i+1。两种体系都可以，只要前后一致。

编号从 0 开始:
root = 0
left = 2*i
right = 2*i + 1

编号的意义不是数组真的存在，而是给每个节点一个“如果它在完全二叉树中会站在哪个位置”的坐标。宽度就可以用坐标差计算。

手推一层会更直观。根节点编号 0，它的左孩子编号 0、右孩子编号 1；下一层中，左孩子的左孩子编号 0，左孩子的右孩子编号 1，右孩子的左孩子编号 2，右孩子的右孩子编号 3。即使中间两个节点不存在，只要最左是 0、最右是 3，这一层宽度就应该是 4。

编号坐标:   0     1     2     3
节点存在:   5    空    空     9
宽度跨度:   <----------- 4 ----------->

这也是为什么编号不用真的建一个数组。数组只是帮助我们定义位置，真正存储的还是非空节点和它们的坐标。

三、每层宽度为什么是 last - first + 1

同一层的节点按从左到右出队。第一个非空节点的位置是 first，最后一个非空节点的位置是 last，两端之间的位置数量就是 last - first + 1。这个公式会自然包含中间空位。

first	last	宽度
0	0	1
0	1	2
0	3	4
2	6	5

如果某层只有一个节点，首尾编号相同，宽度就是 1。这个边界也能验证公式没有少加 1。

注意公式里的 +1 很容易漏。last - first 算的是两个坐标之间隔了多少步，而不是包含端点后的数量。例如坐标 0 到坐标 3，中间有 3 段距离，但位置数量是 0、1、2、3 共 4 个。很多 off-by-one 错误都来自把“距离”和“数量”混成一件事。

四、为什么要做编号归一化

树很深时，按 2*i+1 不断扩大会导致编号溢出。比如深度 63 时，编号可能接近 2^63，超过 long 正数范围。每一层只关心本层节点之间的相对距离，所以可以减去本层第一个编号，把它归一化为 0。

原编号: [1024, 1027]
归一化: [0, 3]
宽度仍为 3 - 0 + 1 = 4

归一化不会改变同层节点之间的距离，却能让下一层编号保持较小，是这题的常见工程细节。

归一化的做法通常是在每层开始取 base = q.peek().idx，本层所有节点都先计算 idx = rawIdx - base。这样本层第一个节点永远从 0 开始，后续孩子编号也基于较小的相对编号生成。它不会影响宽度，因为同层所有坐标都减去了同一个数，首尾差保持不变。

原始首尾: rawFirst=1024, rawLast=1027
统一减 base=1024
相对首尾: first=0, last=3
宽度: 1027-1024+1 = 3-0+1 = 4

这个细节的代价是代码多一个 base，收益是避免深树指数编号溢出，属于很值得主动说明的工程边界。

五、BFS 与 DFS 两种写法

BFS 更直观，因为它天然按层拿到首尾编号。DFS 也可以做：记录每一深度第一次出现的编号，后续同深度节点用当前编号减首编号更新宽度。DFS 写法更短，但要更注意编号溢出和深度数组。

写法	保存信息	优点	风险
BFS	队列中节点和编号	层边界清晰	宽树队列大
DFS	每层最左编号	代码简洁	深树递归栈风险

面试中只要能解释“编号用于保留空位”，选择 BFS 或 DFS 都可以。

DFS 写法的关键是“每层第一次看到的编号就是这一层的最左编号”。如果先访问左子树，再访问右子树，这个结论成立；如果访问顺序乱了，就不能直接用第一次访问当最左边界。BFS 则不需要依赖递归顺序，因为队列按层从左到右天然给出首尾节点。实际答题时，BFS 代码更长一点，但思维负担更低；DFS 代码更紧凑，但更考验你对遍历顺序和深度状态的掌控。

六、常见误区与追问

易错点：最大宽度要数空位，所以队列长度不是答案，位置编号才是答案。

误区：当前层队列大小就是宽度。 队列只包含非空节点，中间空位会被漏掉。
误区：编号从 0 或 1 开始会影响答案。 只要孩子公式一致，同层差值不受影响。
误区：不需要考虑溢出。 深树中编号指数增长，建议每层归一化并用 long。
追问：DFS 怎么写？ 每层记录第一次访问到的编号，当前宽度为 idx - first[depth] + 1。
追问：为什么空树宽度是 0？ 没有任何层，也就没有可见宽度。
追问：最大宽度和最大节点数有什么区别？ 最大节点数只数非空节点，最大宽度按位置包含空洞。

七、加强记忆

这题要把树想成“压在完全二叉树数组上”。节点是否存在是一回事，节点位置是另一回事；宽度看的正是位置跨度。BFS 给每个节点带编号，每层用首尾编号相减，归一化防溢出，三个动作连起来就能稳定写出答案。

简化版

详细版