题目
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]输入:root = [1]
输出:[[1]]输入:root = []
输出:[]
思路
-
创建一个队列(queue)用于存储待处理的二叉树节点。
-
将根节点放入队列中。
-
开始进行层序遍历:
- 当队列不为空时,表示还有节点需要处理。
- 每次处理一层的节点时,先获取当前队列的大小,这个大小即为当前层的节点数目。
- 遍历当前层级的节点:
- 依次取出队首的节点,将其值存入当前层级的结果中。
- 如果该节点有左子节点,将左子节点加入队列。
- 如果该节点有右子节点,将右子节点加入队列。
- 将每一层的节点值存入最终的结果中,直至队列为空,完成整个层序遍历。
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;}
};