【力扣】二叉树的分层遍历1和2
2023-09-27 14:29:24 时间
二叉树的分层遍历1
链接:二叉树的分层遍历1:
首先,我们需要知道什么是二叉树的层序遍历。二叉树的层序遍历是一种按照树的层次从上到下,从左到右访问每个节点的方法。例如,对于下面这棵二叉树:
1
/ \
2 3
/ \
4 5
它的层序遍历结果是:[1, 2, 3, 4, 5]。
那么,如何实现这种遍历方法呢?我们可以使用一个队列来辅助我们。队列是一种先进先出(FIFO)的数据结构,也就是说,先进入队列的元素会先出队,后进入队列的元素会后出队。
我们的思路是这样的:
- 首先,我们判断根节点是否为空,如果为空,就直接返回一个空的二维向量作为结果。
- 如果不为空,我们就把根节点入队,并记录当前层的节点数为1(因为只有根节点一个节点)。
- 然后,我们开始一个循环,直到队列为空为止。在每次循环中,我们做以下几件事:
- 创建一个一维向量来存储当前层的节点值。
- 使用一个内层循环来遍历当前层的所有节点。在每次内层循环中,我们做以下几件事:
- 将队首的节点出队,并将其值放入一维向量中。
- 判断该节点是否有左右子节点,如果有,就将它们入队。
- 当内层循环结束时,说明当前层的所有节点都已经处理完毕,将一维向量放入二维向量中。
- 更新下一层的节点数为队列中剩余的元素个数。
- 当外层循环结束时,说明队列中已经没有元素了,也就是说所有层都已经遍历完毕,返回二维向量作为结果。
这样,我们就实现了二叉树的层序遍历算法。
代码(已加注释):
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) { // 定义一个公共的函数,接受一个二叉树的根节点作为参数,返回一个二维向量,表示每一层的节点值
queue<TreeNode*> q; // 定义一个队列来存储每一层的节点
int levelsize =0; // 定义一个变量来记录当前层的节点数
if(root) // 判断根节点是否为空
{
q.push(root); // 如果不为空,就把根节点入队
levelsize = 1; // 并将当前层的节点数设为1
}
vector<vector<int>> vv; // 定义一个二维向量来存储结果
while(! q.empty()) // 使用一个循环来处理队列中的节点,直到队列为空为止
{
//通过levelsize控制一层一层出
vector<int> v; // 定义一个一维向量来存储当前层的节点值
while(levelsize --) // 使用一个内层循环来遍历当前层的所有节点
{
TreeNode* front = q.front(); // 将队首的节点出队,并保存到一个临时变量中
q.pop();
v.push_back(front->val); // 将该节点的值放入一维向量中
// 带入下一层的节点
if(front->left) // 判断该节点是否有左子节点
q.push(front->left); // 如果有,就将其入队
if(front->right) // 判断该节点是否有右子节点
q.push(front->right); // 如果有,就将其入队
}
vv.push_back(v); // 当内层循环结束时,说明当前层的所有节点都已经处理完毕,将一维向量放入二维向量中
//更新下一层的数据
levelsize = q.size(); // 将下一层的节点数设为队列中剩余的元素个数
}
return vv; // 当外层循环结束时,说明队列中已经没有元素了,也就是说所有层都已经遍历完毕,返回二维向量作为结果
}
};
二叉树的分层遍历2
链接:层序遍历2 — 自底向上
这个其实很简单,把自上而下遍历的结果逆置一下就行了,复用了
代码:
//....前面一样
reverse(vv.begin(),vv.end() ); //逆置一下
return vv; // 当外层循环结束时,说明队列中已经没有元素了,也就是说所有层都已经遍历完毕,返回二维向量作为结果
}
};
本节完
相关文章
- 【华为OD机试真题 python】创建二叉树【2023 Q1 | 200分】
- 二叉树的中序遍历
- 二叉树的层序遍历 II
- 对称的二叉树
- 判断二叉树是否为完全二叉树
- 【Leetcode】102. 二叉树的层序遍历(中等)
- 五三想休息,今天还学习,图解二叉树的层序遍历BFS(广度优先)模板,附面试题题解
- 【数据结构】二叉树的遍历:前序,中序,后序的递归结构遍历
- 【LeetCode】二叉树的遍历与构建问题
- 二叉树与b树的性能区别:计算、层级与io
- LeetCode 103. 二叉树的锯齿形层序遍历
- LeetCode098之验证二叉搜索树(相关话题:二叉树中序遍历的应用)
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 【数据结构/二叉树/二叉树遍历】题解+详细备注(共14题)
- 已知二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列
- 面试题23_从上往下打印二叉树
- 求二叉树的先序遍历
- 二叉树的前序、中序、后序、层序遍历
- [LeetCode] 979. Distribute Coins in Binary Tree 在二叉树中分配硬币
- [LeetCode] 971. Flip Binary Tree To Match Preorder Traversal 翻转二叉树以匹配先序遍历
- [LeetCode] 968. Binary Tree Cameras 二叉树相机
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] 112. Path Sum 二叉树的路径和
- LeetCode根据前序与中序、中序与后序,前序与后序遍历序列构建二叉树
- PAT归纳总结——关于二叉树的一些总结