102.二叉树的层序遍历
力扣链接https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
题目描述:
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
思路分析:
层序遍历与前面讲的递归实现二叉树的遍历属于不同思想。层序遍历属于广度优先搜索,而前面讲的递归遍历属于深度优先搜索。
层序遍历可以借助单向队列来实现。队列先进先出的特性,与按层次进行元素的先后遍历刚好思想统一。二叉树通过指针来实现树的构建,所以队列里面存的应该是指向节点的指针,而且遍历开始时存放的应该是根节点对应的指针。
在记录完根节点对应的元素后,应该将根节点对应的左右子节点的指针入队(为下一层遍历做准备),同时将根节点指针出队(已经记录过了)。
此外,对于较深的层,其节点数可能不唯一,这时候就需要在对每一层遍历前先进行节点数统计(其数值就是队列的长度),然后使用循环依次遍历各节点,接着该节点的指针出队。
具体代码如下:
/**
* 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) {
queue<TreeNode* > que;
//二维vector用存放每一层的节点,其中同一层的节点存放在一个一维的vector中
vector<vector<int>> result;
if(root != nullptr) //如果树非空,则根节点先入队
que.push(root);
else
return result; //否则,直接return空的result
//只要队列不为空,说明还有节点未遍历,所以使用while循环
while(!que.empty())
{
int size = que.size(); //记录当前层的节点数,有几个指针,就对应几个节点
vector<int> vec; //用于记录当前层中的节点元素
for(int i = 0; i < size; i++) //循环控制当前层每个节点元素的提取
{
TreeNode * node = que.front(); //取出队头的节点
vec.push_back(node->val); //记录该节点对应的元素
que.pop(); //记录完毕,节点出队
//下面要将该节点的左右子节点入队,为下一层的提取作准备
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
//将当前层的结果加入最终的结果中
result.push_back(vec);
}
return result;
}
};