二叉树最大宽度 图解题解

这道题到底在问什么

树

[1,3,2,5,3,null,9]

第1层

1 → 宽度 1

第2层

3 2 → 宽度 2

第3层

5 3 _ 9 → 宽度 4

答案

4

最优解：一步一步想明白

1. 3难点就在空位。第 3 层有 5、3、9 三个节点，但它们不是一路挨着的——3 和 9 中间空了一格。怎么把这个「空隙」量出来、算进宽度里？
2. 4妙处在这：哪怕中间有空缺，座位号照样连续递增。一层最右节点的编号减最左节点的编号，再加 1，正好就是这层的宽度——空位自动被算进去了。
3. 5每层进队列时，第一个出队的就是最左、最后一个出队的就是最右。它俩的编号一减一加，就是这层宽度。下面用 [1,3,2,5,3,null,9] 这棵树一帧一帧地走。
4. 6ans = 0，根编号 = 0这是例子树。注意第 3 层：5 在最左、9 在最右，中间空了位置。我们给每个节点编号（根=0，左孩子=2i，右孩子=2i+1），用 BFS 逐层算宽度。一帧一个动作，盯住右边面板里的编号。
5. 7queue = [1·0]先把根 1 放进队列，给它编号 0。蓝色表示「已在队列、等待处理」。BFS 的规矩是一层处理完再下一层。
6. 8本层 first = 0处理第 1 层。这层只有根 1。它第一个出队，所以记下本层 first（最左编号）= 0。橙色的 1 是正在处理的节点 cur。
7. 91 的孩子: 3·0, 2·11 把两个孩子带编号塞进队列：左孩子 3 编号 2i=0，右孩子 2 编号 2i+1=1。它俩变蓝（已入队）。1 也是本层最后一个，所以 last 编号 = 0。
8. 10宽度 = 0−0+1 = 1，ans = 1第 1 层处理完。宽度 = last − first + 1 = 0 − 0 + 1 = 1。更新 ans = 1。根 1 变绿表示这层结清了。继续往下走。
9. 11本层 first = 0进入第 2 层。第一个出队的是 3，编号 0——它是本层最左，记下 first = 0。橙色 cur 标着正在处理它。
10. 123 的孩子: 5·0, 3·1节点 3 把它的两个孩子带编号入队：左孩子 5 编号 2×0=0，右孩子 3 编号 2×0+1=1。它俩变蓝（已入队）。本层 first 早已锁定 0。继续取本层下一个。
11. 13cur = 2·编号1，last = 1本层下一个出队的是 2，编号 1。它是本层最后一个，所以记下 last = 1。3 已处理完变绿，橙色 cur 移到 2。
12. 142 的孩子: 左空(编号2), 9·3节点 2 只有一个右孩子 9，编号 2×1+1=3；它的左孩子是空的，那个编号 2 的座位天生没人坐。但编号不跳号——9 照样拿到它该有的编号 3。现在第 3 层的队列是 5·0、3·1、9·3。
13. 15宽度 = 1−0+1 = 2，ans = 2第 2 层结清：宽度 = last − first + 1 = 1 − 0 + 1 = 2。ans 更新到 2。3、2 都变绿。下面是关键的第 3 层——它有三个节点 5、3、9，中间还夹着一个空位。
14. 16本层 first = 0进入第 3 层，队列里是 5·0、3·1、9·3 三个节点。第一个出队的是 5，编号 0，锁定 first = 0。它是本层最左，靠的就是这个最小的编号。
15. 17cur = 3·编号1本层第二个出队的是中间这个节点 3，编号 1。5 处理完变绿，橙色 cur 移到 3。它俩都是叶子、没孩子入队。first 仍是 0，本层还剩最右的 9 没取，继续。
16. 18cur = 9·编号3，last = 3本层最后一个出队是 9，编号 3，记下 last = 3。注意编号：5 是 0、中间的 3 是 1、9 是 3——9 和 3 之间空了编号 2 那个座位（节点 2 的左孩子是空的），但编号不跳号。5、3 变绿，橙色 cur 到 9。
17. 19宽度 = 3−0+1 = 4本层 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 的来历。
18. 20第3层编号 0,1,(2空),3把第 3 层的座位号摆出来：5 是 0、中间的 3 是 1、9 是 3，而编号 2 那个座位是空的（节点 2 的左孩子缺席）。最左 0、最右 3，宽度 = 3 − 0 + 1 = 4——你看，中间那个空座位 2 被这个差值自动算进去了，根本不用你专门去数它。
19. 21跨度看座位号，不看有没有人看懂编号的灵魂：这一层数节点只有 5、3、9 三个，可宽度是 4。差出来的那个 1，正是中间编号 2 的空座位。最右编号减最左编号加 1，空位被自动算进去了——这就是「编号相减」比「数节点个数」强的地方：跨度看的是座位号，不是有没有人坐。
20. 22队列空，BFS 结束本例 [1,3,2,5,3,null,9] 三层宽度分别 1、2、4，最大宽度 = 4，出在第 3 层。算法核心已演完：每层最右编号 − 最左编号 + 1，取最大。所有节点变绿，BFS 结束。
21. 23深树时编号是 2 的指数级，几十层就超过 int 范围。所以 Java 要用 long，或者每层把编号「归零平移」（减去本层第一个编号）防溢出。下一帧讲归零技巧。
22. 24本层编号都减去 first防溢出小技巧：每处理一层，把这层所有编号都减去本层第一个编号 first，让本层编号从 0 重新开始。差值（宽度）不受影响，但编号不会一直翻倍变大。紫色标出被归零平移的两端。
23. 27一句话记住它：别去数节点个数，去看座位号的跨度。最右座位号减最左座位号加 1，中间空着的座位也算在宽度里，这正是题目要的。
24. 29第3层只数到 3 个 → 漏掉空位看这个错法：第 3 层数到 5、3、9 三个节点，就以为宽度是 3。错——这漏掉了它们之间的空位。正确永远看编号跨度：最右编号减最左编号加 1，空位自动计入。
25. 30把左孩子写成 2i+1 → 座位错位另一个坑：把左右孩子的编号公式写反。左孩子必须是 2i、右孩子必须是 2i+1，写反了同层节点的座位号全乱，宽度自然算错。记牢这个标准编号方向。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        long long ans = 0;
        queue<pair<TreeNode*, unsigned long long>> q;
        q.push({root, 0});                       // (节点, 编号)
        while (!q.empty()) {
            int sz = q.size();
            unsigned long long first = q.front().second; // 本层最左
            unsigned long long last = first;
            for (int i = 0; i < sz; ++i) {
                auto [node, idx] = q.front(); q.pop();
                last = idx;
                idx -= first;                        // 归零防溢出
                if (node->left)  q.push({node->left, idx * 2});       // 左=2i
                if (node->right) q.push({node->right, idx * 2 + 1}); // 右=2i+1
            }
            ans = max(ans, (long long)(last - first + 1));
        }
        return (int)ans;
    }
};

// 编号会指数膨胀，必须用 long 防溢出
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        long ans = 0;
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Long> idxs = new ArrayDeque<>();
        nodes.offer(root);
        idxs.offer(0L);                          // 根编号 0
        while (!nodes.isEmpty()) {
            int sz = nodes.size();
            long first = idxs.peek();            // 本层最左
            long last = first;
            for (int i = 0; i < sz; i++) {
                TreeNode node = nodes.poll();
                long idx = idxs.poll() - first;      // 归零防溢出
                last = first + idx;
                if (node.left != null)  { nodes.offer(node.left);  idxs.offer(idx * 2); }     // 左=2i
                if (node.right != null) { nodes.offer(node.right); idxs.offer(idx * 2 + 1); } // 右=2i+1
            }
            ans = Math.max(ans, last - first + 1);
        }
        return (int) ans;
    }
}

复杂度

面试官可能追问