跳到主要内容

LeetCode 662. 二叉树最大宽度

本节目标

在层序遍历中携带完全二叉树位置编号，用首尾位置跨度计算最大宽度。

这是树上综合问题中给层序状态补上位置坐标的题目。宽度不是本层实际节点数，而是最左和最右非空节点在完整二叉树布局中的跨度。

查看 LeetCode 原题

题意与边界​

将树按满二叉树的位置排列，两个非空节点之间的空位也计入宽度。空树宽度为 0；深链每层只有一个节点，宽度始终为 1。

位置编号与逐层归一化​

给根一个编号，左、右孩子编号分别为 2 * index + 1、2 * index + 2。同一层的宽度就是末编号减首编号加一。若直接从根持续编号，深树会让编号不必要地快速增长。

因此队列保存 (node, index)，每层开始记录队首 base，取出节点后先做 index -= base，再用归一化后的编号生成孩子位置。减去同一个常数不会改变本层的首尾差，却让每层的最左位置从零开始。C++ 使用 unsigned long long 保存编号。

正确性依据​

完全二叉树编号精确保持一层节点之间的空位数量，故首尾编号差加一等于题目宽度。每层统一减去 base 后，任意两节点的位置差不变，孩子编号仍与归一化坐标对应；归一化不改变任何一层的宽度。BFS 恰好逐层枚举所有节点，取各层最大值即为答案。

代码实现​

C++17
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        std::queue<std::pair<TreeNode*, unsigned long long>> queue;
        queue.push({root, 0});
        int answer = 0;
        while (!queue.empty()) {
            int size = static_cast<int>(queue.size());
            unsigned long long base = queue.front().second;
            unsigned long long first = 0;
            unsigned long long last = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = queue.front().first;
                unsigned long long index = queue.front().second - base;
                queue.pop();
                if (i == 0) {
                    first = index;
                }
                last = index;
                if (node->left != nullptr) {
                    queue.push({node->left, 2 * index + 1});
                }
                if (node->right != nullptr) {
                    queue.push({node->right, 2 * index + 2});
                }
            }
            answer = std::max(answer, static_cast<int>(last - first + 1));
        }
        return answer;
    }
};

复杂度分析​

每个节点入队、出队一次，时间复杂度为 O(n)。队列最多保存一层节点，额外空间为 O(w)，其中 w 为最大层实际节点数。

边界与易错点​

  • 把 queue.size() 当作宽度，漏掉中间空位。
  • 忘记按层固定队列长度，混淆下一层编号。
  • 只用窄整数并持续累乘编号，深树可能溢出。
  • 归一化后仍用旧编号生成孩子，失去避免增长的作用。

模式迁移​

层序遍历若要比较横向位置、边界或同层间距，队列就应携带坐标状态。坐标只需保持相对关系时，可在每层做平移或压缩。