LeetCode102.二叉树的层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]输入：root = [1]
输出：[[1]]输入：root = []
输出：[]

思路

1. 创建一个队列（queue）用于存储待处理的二叉树节点。

2. 将根节点放入队列中。

3. 开始进行层序遍历：

• 当队列不为空时，表示还有节点需要处理。
• 每次处理一层的节点时，先获取当前队列的大小，这个大小即为当前层的节点数目。
• 遍历当前层级的节点：
  • 依次取出队首的节点，将其值存入当前层级的结果中。
  • 如果该节点有左子节点，将左子节点加入队列。
  • 如果该节点有右子节点，将右子节点加入队列。

4. 将每一层的节点值存入最终的结果中，直至队列为空，完成整个层序遍历。

Code

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result; // 存储层序遍历的结果if (root == NULL) {return result; // 如果根节点为空，直接返回空的结果}queue<TreeNode*> q;q.push(root); // 将根节点放入队列中// 开始进行层序遍历while (!q.empty()) {int level_size = q.size(); // 获取当前层级的节点数量vector<int> level_values;  // 存储当前层级节点的值// 遍历当前层级的节点for (int i = 0; i < level_size; i++) {TreeNode* node = q.front();q.pop(); // 出队level_values.push_back(node->val); // 存储当前节点的值// 将当前节点的子节点（如果存在）加入队列中if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}result.push_back(level_values); // 将当前层级的节点值存入最终结果中}return result;}
};