文档目录

一、BFS 层序遍历模板（LeetCode 102）

问题：按层打印二叉树，每层一个 vector。

思路：

     3
   /   \
  9    20
      /  \
     15   7

层序遍历结果：
[
  [3],       // 第 0 层
  [9, 20],   // 第 1 层
  [15, 7]    // 第 2 层
]

整体操作流程：

  1. 初始化：如果根节点为空，返回空结果。创建队列并将根节点入队。
  2. 层循环：当队列不为空时，记录当前层的节点数 level_size = q.size()。
  3. 节点循环：从队列中弹出 level_size 个节点：
    • 将节点值加入当前层结果。
    • 将节点的左右子节点入队（这些属于下一层）。
  4. 保存结果：将当前层结果加入最终结果集。
  5. 重复：直到队列为空，所有层遍历完毕。
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};                          // ① 空树 → 空结果

    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);                                  // ② 根节点入队

    while (!q.empty()) {
        int level_size = q.size();                 // ③ 记录当前层节点数
        vector<int> level;

        for (int i = 0; i < level_size; i++) {     // ④ 遍历当前层的所有节点
            TreeNode* node = q.front();
            q.pop();                                // ⑤ 弹出队首节点

            level.push_back(node->val);             // ⑥ 记录节点值

            if (node->left)  q.push(node->left);    // ⑦ 左子节点入队（下一层）
            if (node->right) q.push(node->right);   // ⑧ 右子节点入队（下一层）
        }

        result.push_back(std::move(level));         // ⑨ 保存当前层结果
    }

    return result;
}

关键点：int level_size = q.size() 在循环之前记录当前层大小，保证 for 循环只处理当前层的节点，不混入下一层。

二、BFS 的两种变体

变体 1：二叉树右视图（LeetCode 199）

整体操作流程：

  1. 初始化：空树返回空结果。创建队列，根节点入队。
  2. 层循环：记录当前层节点数 level_size。
  3. 遍历当前层：遍历当前层的每个节点，将子节点入队。
  4. 取右视图：在每层的最后一个节点（i == level_size - 1）时，将其值加入结果集——即二叉树从右侧看能看到的节点。
  5. 重复直到队列为空。
vector<int> rightSideView(TreeNode* root) {
    if (!root) return {};

    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);                                  // ① 根节点入队

    while (!q.empty()) {
        int level_size = q.size();                 // ② 当前层节点数

        for (int i = 0; i < level_size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (i == level_size - 1) {             // ③ 每层的最后一个节点
                result.push_back(node->val);       // ④ 加入右视图结果
            }

            if (node->left)  q.push(node->left);   // ⑤ 子节点入队
            if (node->right) q.push(node->right);
        }
    }

    return result;
}

变体 2：之字形遍历（LeetCode 103）

整体操作流程：

  1. 初始化：空树返回空结果。创建队列，根节点入队。设置方向标志 left_to_right = true。
  2. 层循环：记录当前层节点数。
  3. 遍历当前层：
    • 如果从左到右：将节点值追加到 deque 尾部（正常顺序）。
    • 如果从右到左：将节点值插入到 deque 头部（实现反转）。
    • 子节点入队（保持左右顺序，因为入队顺序不随方向改变）。
  4. 切换方向：每层结束后翻转 left_to_right。
  5. 重复直到队列为空。
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);                                  // ① 根节点入队
    bool left_to_right = true;                     // ② 初始从左到右

    while (!q.empty()) {
        int level_size = q.size();                 // ③ 当前层节点数
        deque<int> level;                          // ④ 双端队列支持前后插入

        for (int i = 0; i < level_size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (left_to_right) {
                level.push_back(node->val);        // ⑤ 从左到右：尾部插入
            } else {
                level.push_front(node->val);       // ⑥ 从右到左：头部插入（反转）
            }

            if (node->left)  q.push(node->left);   // ⑦ 子节点入队
            if (node->right) q.push(node->right);
        }

        result.emplace_back(level.begin(), level.end());// ⑧ 保存当前层
        left_to_right = !left_to_right;            // ⑨ 切换方向
    }

    return result;
}

时间复杂度：均 $O(N)$。每个节点入队一次出队一次。