题目描述

给你一个二叉树，要求你返回其节点值的层序遍历结果（即逐层地，从左到右访问所有节点）。

示例：

输入：3/ \9  20/  \15   7
输出：[[3], [9,20], [15,7]]

解题思路

层序遍历（BFS）的核心思想是利用队列先进先出的特性，逐层处理每个节点。但问题在于如何区分不同层级的节点。这里我们采用一个巧妙的方法：在每层结束时插入一个空指针（nullptr）作为分隔符。

具体步骤如下：

1. 初始化队列：将根节点和nullptr加入队列。nullptr表示第一层结束。
2. 循环处理队列：
   • 取出队首元素。
   • 如果是普通节点：记录其值到临时数组，并将左右子节点入队。
   • 如果是nullptr：说明当前层处理完毕，将临时数组存入结果，清空临时数组。如果队列不为空，说明还有下一层，插入新的nullptr作为分隔符。
3. 终止条件：队列为空时结束循环。

代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {}; // 处理空树deque<TreeNode*> dq;dq.push_back(root);dq.push_back(nullptr); // 第一层结束标记vector<int> tmp;vector<vector<int>> res;while (!dq.empty()) {TreeNode* node = dq.front();dq.pop_front();if (node) { // 普通节点处理tmp.push_back(node->val);if (node->left) dq.push_back(node->left);if (node->right) dq.push_back(node->right);} else { // 遇到分隔符res.push_back(tmp);tmp.clear();if (!dq.empty()) dq.push_back(nullptr); // 下一层结束标记}}return res;}
};

复杂度分析

• 时间复杂度：O(n)，每个节点恰好被访问一次。
• 空间复杂度：O(n)，队列中最多存储两层的节点，但总体是线性空间。

关键点解析

• 分隔符技巧：用nullptr标记层级结束，避免混淆不同层的节点。
• 队列的动态更新：处理完一层后立即插入新的分隔符，确保层级正确划分。
• 边界处理：根节点为空时直接返回空数组，避免无效操作。

通过这种方法，我们可以清晰地将二叉树的每一层节点值收集起来，最终得到符合要求的层序遍历结果。