662. 二叉树最大宽度

LeetCode：662. 二叉树最大宽度
难度：中等
归类：二叉树、广度优先搜索、深度优先搜索
主解法：携带完全二叉树位置编号的分层 BFS

先给结论

本题的"宽度"不是某一层非空节点的数量，而是最左、最右非空节点之间的完整位置数，中间本应存在的 null 位置也要计算。

给节点附加它在本层完整槽位中的虚拟编号：

根节点所在层的位置：0
本层位置 index 的左孩子在下一层的位置：2 × index
本层位置 index 的右孩子在下一层的位置：2 × index + 1

同一层最左节点位置为 first、最右节点位置为 last 时：

该层宽度 = last - first + 1

按层 BFS 可以直接得到每层的左右端点。为了避免深树中的位置编号指数增长，每处理一层都减去本层第一个编号，再基于归一化后的编号生成下一层位置。

题目描述

给定一棵二叉树，返回所有层中的最大宽度。

某一层的宽度定义为：该层最左和最右非空节点之间的长度。把二叉树补成具有相同结构位置的满二叉树后，两个端点之间的 null 位置也计入宽度。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4

第三层的位置为：

5, 3, null, 9

虽然只有 3 个非空节点，宽度仍然是 4。

示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7

示例 3：

输入：root = [1,3,2,5]
输出：2

题目约束：

树中节点数为 [1, 3000]。
-100 <= Node.val <= 100。
答案保证在 32 位带符号整数范围内。

代码额外兼容空树，返回 0。

为什么只统计节点数不够

考虑：

第三层只有节点 4 和 5，但按照完全二叉树的位置，它们之间还有两个空位：

4, null, null, 5

因此宽度是 4，不是 2。

如果队列中只保存节点，就会丢失空位信息。没有必要真的把所有 null 入队；保存虚拟位置编号即可恢复端点之间的距离。

完全二叉树的层内位置编号

每一层的完整槽位都从 0 开始编号。父节点在当前层的位置为 index 时，它的孩子在下一层的位置如下：

父节点位置	左孩子位置	右孩子位置
`0`	`0`	`1`
`1`	`2`	`3`
`2`	`4`	`5`

同一层中，实际存在的节点仍按从左到右顺序进入数组。即使某些中间位置为空，最左和最右编号之差仍会保留这些空位。

节点值与宽度无关，不参与计算。

为什么要按层归一化编号

如果从根节点开始不断使用 2 × index 和 2 × index + 1，一条很深的右链会产生接近 2^depth 的编号。JavaScript 的 Number 只能精确表示不超过 2^53 - 1 的整数，直接编号可能失去精度。

处理某层时，将所有位置都减去该层最左位置：

normalized = index - firstIndex

减去同一个常数不会改变位置差：

(last - first) ===
(last - firstIndex) - (first - firstIndex)

生成孩子时使用归一化编号，相当于把下一层所有原始编号统一减去 2 × firstIndex，孩子之间的相对距离仍然不变。

归一化后，本层编号范围是 [0, width - 1]。题目保证最大宽度不超过 32 位带符号整数，下一层生成的临时编号小于 2^32，远低于 Number 的安全整数上限，因此不需要 BigInt。

BFS 状态与不变量

level 保存当前层的所有 [node, index]，并满足：

节点按从左到右顺序排列。
index 保留这些节点在完全二叉树中的相对位置。
同一层所有编号采用相同的平移基准，所以编号差等于真实位置差。

处理一层时：

first 取第一个节点的位置。
last 取最后一个节点的位置（因为数组从左到右排列，末尾就是最右）。
本层宽度直接由 last - first + 1 得到。
子节点根据 2 × normalized 和 2 × normalized + 1 加入 nextLevel。

每轮完整处理一层后，再让 level = nextLevel。

示例推演

以 root = [1,3,2,5,3,null,9] 为例：

层	非空节点	归一化位置	宽度
`1`	`1`	`[0]`	`1`
`2`	`3, 2`	`[0, 1]`	`2`
`3`	`5, 3, 9`	`[0, 1, 3]`	`3 - 0 + 1 = 4`

第二层位置 [0, 1] 生成孩子位置：

节点 3 的左、右孩子位置：0、1
节点 2 的左、右孩子位置：2、3

节点 2 没有左孩子，但右孩子 9 仍保留位置 3，所以第三层中间的空位会被计入。

算法步骤

空树返回 0。
用 [[root, 0]] 初始化当前层。
读取本层第一个位置作为归一化基准，最后一个位置作为最右端点。
用 last - first + 1 更新最大宽度。
按归一化位置计算左右孩子编号，加入下一层。
继续处理下一层，直到没有节点。

代码实现

思路参考：JoshCrozier/leetcode-javascript。本文将队列改为逐层数组，避免 Array.shift() 的线性移动，并通过逐层编号归一化避免使用无限增长的 BigInt；原项目采用 MIT License。

JavaScript 实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val);
 *     this.left = (left === undefined ? null : left);
 *     this.right = (right === undefined ? null : right);
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function (root) {
    if (!root) {
        return 0;
    }

    let level = [[root, 0]];
    let maxWidth = 1;

    while (level.length > 0) {
        const first = level[0][1];
        const last = level[level.length - 1][1];
        maxWidth = Math.max(maxWidth, last - first + 1);

        const nextLevel = [];
        for (const [node, index] of level) {
            const normalized = index - first;

            if (node.left) {
                nextLevel.push([node.left, normalized * 2]);
            }
            if (node.right) {
                nextLevel.push([node.right, normalized * 2 + 1]);
            }
        }

        level = nextLevel;
    }

    return maxWidth;
};

DFS 替代写法

如果不在意递归，DFS 的代码可以短到 10 行：

var widthOfBinaryTree = function (root) {
    const leftmost = [];
    let ans = 0;

    const dfs = (node, depth, index) => {
        if (!node) return;
        if (leftmost[depth] === undefined) leftmost[depth] = index;
        ans = Math.max(ans, index - leftmost[depth] + 1);
        dfs(node.left,  depth + 1, index * 2);
        dfs(node.right, depth + 1, index * 2 + 1);
    };

    dfs(root, 0, 0);
    return ans;
};

非常直观：第一次到达某深度时记录最左位置，之后每到一个节点就计算当前宽度。但要注意，极端斜树的 index 会指数增长到 2^3000，远超 JavaScript 安全整数范围。稳妥做法是把 index 改为 BigInt：

dfs(node.left, depth + 1, index * 2n);
ans = Math.max(ans, Number(index - leftmost[depth] + 1n));

代码与思路对照

代码	作用
`level[0][1]`	取得本层最左非空节点的位置
`level[level.length - 1][1]`	取得本层最右非空节点的位置（数组天然从左到右排列）
`last - first + 1`	计算包含中间空位的本层宽度
`index - first`	将本层最左位置归零，控制编号大小
`normalized * 2`	计算左孩子的相对位置
`normalized * 2 + 1`	计算右孩子的相对位置
`level = nextLevel`	保持严格的逐层处理顺序

正确性说明

位置编号正确表示空位

在完整二叉树的层内编号中，左右孩子公式会为下一层的每个结构位置分配唯一编号。即使某个节点不存在，它占据的位置仍会体现在同层其他节点的编号间隔中。

因此，同层最右编号减最左编号再加一，恰好等于题目定义的宽度。

归一化不改变宽度

同层所有编号减去同一个 first，任意两个节点的编号差不变。下一层孩子编号也只是相对原始编号整体平移 2 × first，所以孩子之间的编号差同样不变。

因此每层使用归一化编号仍能得到真实宽度。

BFS 不会漏掉任何层

BFS 每轮处理 level 的全部节点，并把它们所有非空孩子加入 nextLevel。每个节点恰好进入一次对应层数组，每一层都会计算一次宽度。

算法对所有层宽度取最大值，所以返回值就是整棵树的最大宽度。

边界与陷阱

宽度不是节点数： 中间的 null 位置必须计入。
空树： 虽然题目保证至少一个节点，代码仍兼容 root === null。
单节点和单链： 每层宽度都是 1。
极深右链： 不归一化会让编号指数增长；归一化后每层重新从 0 开始。
稀疏双侧分支： 节点很少也可能拥有很大宽度，不能只根据队列长度更新答案。
不要真的入队 null： 深度增加时空节点数量会指数膨胀。
固定处理整层： 子节点只能进入下一层，不能与当前层混算。
不要使用 Array.shift()： JavaScript 数组头删需要移动后续元素，反复调用可能退化到 O(n²)。
左右孩子编号不能写反： 本文采用左 2i、右 2i + 1 的零基编号。
节点值无关： 负数、重复值都不影响结构宽度。

复杂度分析

设树中有 n 个节点，某一层最多有 w 个非空节点：

每个节点恰好处理一次，时间复杂度为 O(n)。
level 和 nextLevel 最多保存相邻两层节点，空间复杂度为 O(w)，最坏为 O(n)。

逐层数组不执行头删，每次遍历和追加都是线性总成本。原实现反复调用 queue.shift()，单次头删最坏需要移动队列中其余元素，因此不能直接把那份 JavaScript 实现的最坏时间标成 O(n)。

替代解法

BigInt 编号

也可以保留从根开始的绝对编号并全部使用 BigInt。这样无需依赖数值上界，但算术和类型转换更繁琐。无论是否使用 BigInt，队列都不应反复调用 shift()。

面试官递进追问

1. 为什么本层宽度不能直接使用队列长度？

队列只保存非空节点，而题目还计算最左、最右节点之间的空位置。例如 [5,3,null,9] 只有 3 个节点，宽度却是 4。

2. 完全二叉树编号如何保留空位？

父位置为 i 时，左右结构位置固定为 2i 和 2i + 1。缺失节点虽然不入队，但其他节点的编号不会向前压缩，所以编号差仍包含空位。

3. 为什么每层减去最左编号不会改变答案？

宽度只依赖最右和最左编号的差。同层所有编号减去相同常数后，这个差完全不变。

4. 为什么生成下一层孩子时也能使用归一化编号？

若父节点统一减去常数 c，其孩子编号会统一比原编号少 2c。所有孩子只是整体平移，相对位置和宽度都不变。

5. 为什么这里可以安全使用 JavaScript`Number`？

归一化后本层最大编号是 width - 1，生成孩子时至多扩大到小于 2 × width。题目保证所有层宽度在 32 位带符号整数范围内，因此中间值远小于 2^53 - 1。

6. 为什么不把`null` 节点也加入队列？

虚拟编号已经记录空位。显式扩展 null 会使节点槽位随深度指数增长，而且还需要判断何时停止，没有必要。

7. 原代码使用`shift()` 为什么可能破坏`O(n)` 复杂度？

普通 JavaScript 数组不是专用队列，从头删除元素通常要移动或重排后续元素。连续对大量节点执行可能产生平方级总成本；逐层数组或头指针可以避免。

8. BFS 与 DFS 方案如何取舍？

BFS 天然同时持有一层的左右端点，且没有递归栈风险；DFS 只需记录每层第一个编号，但要携带深度和位置，并注意深树的递归与编号溢出。

常见错误

把某层非空节点数当成宽度。
为了保留空位而把大量 null 真正加入队列。
使用绝对 Number 编号，在深树中超过安全整数范围。
归一化父节点后，却混用未归一化的孩子公式。
宽度忘记加 1。
当前层尚未处理完就把下一层节点纳入宽度。
使用 shift() 却未经分析直接宣称 JavaScript 实现是 O(n)。
DFS 版本没有考虑深度接近 3000 时的调用栈风险。

可迁移总结

虚拟位置： 不必显式保存空节点，只需保存能反映结构间隔的位置编号。
统一平移： 只关心坐标差时，可以减去公共基准控制数值范围。
分层处理： 同层端点信息适合 BFS，每层独立计算。
一句话记忆： BFS 携带完全二叉树编号，每层宽度取最后编号减第一个编号加一，并逐层归一化防溢出。

刷题后自测

先只回答第 1 题，再展开后续问题：

为什么第三层 [5,3,null,9] 的宽度是 4，而不是 3？

一条深度很大的右链中，每层归一化后的位置会是多少？

如果父节点位置统一减去 c，孩子位置为什么会统一减去 2c？

尝试把逐层数组改成"单数组 + 头指针"，并保持每层大小固定。

ON THIS PAGE

#662. 二叉树最大宽度

#先给结论

#题目描述

#为什么只统计节点数不够

#完全二叉树的层内位置编号

#为什么要按层归一化编号

#BFS 状态与不变量

#示例推演

#算法步骤

#代码实现

#JavaScript 实现

#DFS 替代写法

#代码与思路对照

#正确性说明

#位置编号正确表示空位

#归一化不改变宽度

#BFS 不会漏掉任何层

#边界与陷阱

#复杂度分析

#替代解法

#BigInt 编号

#面试官递进追问

#1. 为什么本层宽度不能直接使用队列长度？

#2. 完全二叉树编号如何保留空位？

#3. 为什么每层减去最左编号不会改变答案？

#4. 为什么生成下一层孩子时也能使用归一化编号？

#5. 为什么这里可以安全使用 JavaScriptNumber？

#6. 为什么不把null 节点也加入队列？

#7. 原代码使用shift() 为什么可能破坏O(n) 复杂度？

#8. BFS 与 DFS 方案如何取舍？

#常见错误

#可迁移总结

#刷题后自测