题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解答
- 使用队列辅助层序遍历
注意看这个题的输入与输出，输出的动态数组的元素是元素为整型的数组，比如[[3],[9,20],[15,7]].因此如果只定义一个队列辅助遍历，无法清晰的区分每层的元素应该插入到哪个数组中，比如如果只使用一个队列进行层次遍历，得到的结果只能是[3,9,20,15,7]，无法从这个结果中得知清晰的二叉树层次结构，所以在这里定义两个队列，首先向一个队列中塞入元素，接着对队首元素进行pop并且将队首元素的左右子树节点分别塞入另一队列中，再将结果数组并入result数组中，再将另一个队列进行同样的遍历操作，具体的C++实现代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
// 定义两个队列 分别为q和another_q 用于层次遍历
queue<TreeNode*> q;
queue<TreeNode*> another_q;
// 定义结果数组 其元素为元素为int类型的数组
vector<vector<int>> result;
// 若根节点非空 则将根节点push进队列q中
if (root != nullptr) {
q.push(root);
}
// 当q或者another_q队列非空时 进行遍历操作
while (!q.empty()|| !another_q.empty()) {
// 定义元素为int的临时数组 用于存储每一层的元素
vector<int> temp_vector;
// 当队列q非空时 将队列q的元素逐个出队
while (!q.empty()) {
TreeNode* temp_node = q.front();
// 向临时数组中塞入节点的值
temp_vector.push_back(temp_node->val);
// 塞入之后 将对应元素出队
q.pop();
// 判断出队的元素是否有左右节点并将其塞入另一个队列中
if (temp_node->left != nullptr) {
another_q.push(temp_node->left);
}
if (temp_node->right != nullptr) {
another_q.push(temp_node->right);
}
}
// 若临时数组非空 则将其插入结果数组中 并清空临时数组
if (temp_vector.size() != 0) {
result.push_back(temp_vector);
temp_vector.clear();
}
// 当另一个队列another_q非空时 将队列another_q的元素逐个出队
while (!another_q.empty()) {
TreeNode* temp_node = another_q.front();
// 向临时数组中塞入节点的值
temp_vector.push_back(temp_node->val);
// 塞入之后 将对应元素出队
another_q.pop();
// 判断出队的元素是否有左右节点并将其塞入另一个队列中
if (temp_node->left != nullptr) {
q.push(temp_node->left);
}
if (temp_node->right != nullptr) {
q.push(temp_node->right);
}
}
// 若临时数组非空 则将其插入结果数组中 并清空临时数组
if (temp_vector.size() != 0) {
result.push_back(temp_vector);
temp_vector.clear();
}
}
// 返回结果数组
return result;
}
};