层序遍历?套模板就够了
发布于 2021-01-18 11:23
1.树的层序遍历
顾名思义,对于树型结构,层序遍历就是按层从上到下,每层按一定顺序对树的节点进行遍历。我们通过如图所示的二叉树进行说明:对于左边的二叉树,按层划分后可得到右边的分层结构。
如果按照每层从左到右的遍历逻辑,这棵二叉树的层序遍历序列就是 。通过代码如何实现呢?一般地,我们利用队列 作为容器,按照如下逻辑进行遍历:
// 0. 声明队列
queue<TreeNode*> q;
// 1. 将根节点加入队列
q.push(root);
// 2. 遍历队列中每个节点
while(!q.empty()) {
TreeNode* cur = q.front();
q.pop();
// 3. 记录当前节点值
vec.push(cur->val);
// 4. 将左右孩子放入队列
q.push(cur->left);
q.push(cur->right);
}
一般地,在遍历完第 层的最后一个节点后,该层所有节点都被弹出了队列,且其孩子节点(均处于 层)都被存入了队列且未处理,所以当前队列的长度就是 层的节点数量。
所以,通过
特别地,为了防止二叉树为空、遍历到叶节点等情况,需要加入一些特判元素。修改后的模板如下:
// 1.初始化
queue<TreeNode*> q;
if(root == NULL) { // 二叉树为空
return;
}
q.push(root);
// 2.遍历整棵树
while(1) {
int cnt = q.size();
if(cnt == 0) break; // 已经遍历完二叉树
// 3.遍历该层
while(cnt--) {
TreeNode* cur = q.front();
q.pop();
// 4.对 cur 的操作,根据题意更改
action(cur);
// 5.将左右孩子放入队列
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
2.几道例题
说明:对于不同的题目,只需要在我们的模板基础上增加或更改一些元素,所以对于下面的每道例题,我们在代码中只重点注释修改的部分。
我们先从基础的力扣102题来入手:
题目要求返回一个二维容器,其中的每一个容器记录着某一层的所有节点值。我们只需要层序遍历二叉树,并按层遍历节点,将其加入。在遍历完该层后,将记录了该层所有节点的 加入结果容器即可,代码如下:
vector<vector<int>> levelOrder(TreeNode* root) {
// 声明结果二维容器
vector<vector<int>> result;
queue<TreeNode*> q;
if(root == NULL) return result;
q.push(root);
while(1) {
int cnt = q.size();
if(cnt == 0) break;
// 记录该层节点的容器
vector<int> v;
while(cnt--) {
TreeNode* cur = q.front();
q.pop();
// 将当前节点存入容器
v.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
// 处理完该层,加入结果容器
result.push_back(v);
}
return result;
}
与上一道题不同,要求从下到上遍历。实际上我们只需要从上向下遍历后,将结果容器翻转即可。C++的标准库STL给我们提供了容器翻转的函数:
与前两题不同,对于给定的如图所示的树,锯齿形遍历需要偶数层从右向左返回结果,奇数层从左向右返回结果,也即返回的结果序列应为:
[
[3],
[20,9],
[15,7]
]
本质上,我们只需要
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
// 当前层是否需要翻转
bool flag = false;
queue<TreeNode*> q;
if(root == NULL) return result;
q.push(root);
while(1) {
int cnt = q.size();
if(cnt == 0) break;
vector<int> v;
while(cnt--) {
TreeNode* cur = q.front();
q.pop();
v.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
// 判断是否翻转
if(flag) reverse(v.begin(), v.end());
result.push_back(v);
// 取反
flag = !flag;
}
return result;
}
这是力扣第104题,看下题目:
在我们的模板里,每处理完一层,才退出内层循环,并开始新一轮外层循环。而本题要找最大深度,就是找一共处理了多少层,所以提前维护一个记录层数的变量 ,然后在外层循环内每次增加该变量即可:
int maxDepth(TreeNode* root) {
int depth = 0; // 声明深度
queue<TreeNode*> q;
if(root == NULL) return 0;
q.push(root);
while(1) {
int cnt = q.size();
if(cnt == 0) break;
depth++; // 处理新一层前深度自加
while(cnt--) {
TreeNode* cur = q.front();
q.pop();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
return depth;
}
特别地, 语句必须要放在判断 的语句之后,否则若遍历到最后一层,深度自加之后才会退出循环,导致结果错误。
第111题要求“最小深度”(找到离根节点最近的叶子节点),由于我们进行的是层序遍历,
int minDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> q;
if(root == NULL) return 0;
q.push(root);
while(1) {
int cnt = q.size();
if(cnt == 0) break;
depth++;
while(cnt--) {
TreeNode* cur = q.front();
q.pop();
// 叶子节点
if(!cur->left && !cur->right) return depth;
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
return depth;
}
最后总结
层序遍历的关键,要明确每一轮循环的具体过程。
如果本文讲的层序遍历对你有一些启发,请三连支持作者~~~
推荐阅读
第 222 场周赛 题解2021全新开启
后台回复关键词「进群」可加入交流群。
本文来自网络或网友投稿,如有侵犯您的权益,请发邮件至:aisoutu@outlook.com 我们将第一时间删除。
相关素材