#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。

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

考虑：

        1
       / \
      2   3
     /     \
    4       5

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

4, null, null, 5

因此宽度是 4，不是 2。

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

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

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

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

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

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

如果从根节点开始不断使用 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。

#为什么根是 0，孩子公式却不是 2i + 1 和 2i + 2

如果维护整棵树的全局零基索引，公式确实应该是：

左孩子全局索引 = 2 × index + 1
右孩子全局索引 = 2 × index + 2

但本文代码生成孩子之前，先将当前层编号减去本层最左编号：

normalized = index - first

代码此后保存的不再是全局索引，而是每层归一化后的相对位置。可以从全局零基公式推导出相对位置公式。

下一层统一以本层最左节点的左孩子位置 2 × first + 1 为基准。左孩子归一化后的编号为：

(2 × index + 1) - (2 × first + 1)
= 2 × (index - first)
= 2 × normalized

右孩子归一化后的编号为：

(2 × index + 2) - (2 × first + 1)
= 2 × (index - first) + 1
= 2 × normalized + 1

所以本文使用：

左孩子相对位置 = 2 × normalized
右孩子相对位置 = 2 × normalized + 1

初始化时根节点编号为 0，只是因为第一层只有一个节点，它的全局零基索引和层内相对位置恰好都是 0。从生成下一层开始，代码维护的是层内相对位置，而不是整棵树中唯一的全局索引。

#BFS 状态与不变量

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

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

处理一层时：

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

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

#示例推演

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

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

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

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

#算法步骤

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

#代码实现

思路参考：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) {
    // 空树没有任何一层，最大宽度为 0
    if (!root) {
        return 0;
    }

    // level 保存当前层的 [节点, 虚拟位置编号]
    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;
};

#单数组加 head 实现

也可以使用一个数组保存所有入队节点，再用 head 指向当前尚未处理的队头。进入每一层时，必须基于 head 读取当前层最左节点，不能使用 queue[0]，因为已经处理过的节点不会从数组中删除。

var widthOfBinaryTree = function (root) {
    if (!root) {
        return 0;
    }

    // queue 保存 [节点, 虚拟位置编号]，head 模拟队头
    const queue = [[root, 0]];
    let head = 0;
    let maxWidth = 1;

    while (head < queue.length) {
        // 此时队列中尚未处理的节点恰好都属于当前层
        const levelSize = queue.length - head;

        // 此时 head 指向当前层最左节点，数组末尾就是当前层最右节点
        // 必须在下面的 for 循环加入下一层节点之前读取 last
        const first = queue[head][1];
        const last = queue[queue.length - 1][1];
        maxWidth = Math.max(maxWidth, last - first + 1);

        for (let i = 0; i < levelSize; i++) {
            const [node, index] = queue[head++];

            // 以当前层最左编号为基准归一化，控制下一层编号大小
            const normalized = index - first;

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

    return maxWidth;
};

levelSize 必须在处理本层前固定。内层循环加入的孩子属于下一层，不应在本轮继续处理。

这种写法避免了每层创建 nextLevel 数组，但已经处理过的节点引用会一直保留在 queue 中，因此队列数组最终包含全部 n 个节点，辅助空间为 O(n)。逐层数组实现只同时保留当前层和下一层，辅助空间为 O(w)。

#DFS 替代写法

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

var widthOfBinaryTree = function (root) {
    // leftmost[depth] 记录每一层第一次访问到的最左节点编号
    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));

#代码与思路对照

#正确性说明

#位置编号正确表示空位

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

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

#归一化不改变宽度

同层所有编号减去同一个 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 题，再展开后续问题：

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