关键词:
二叉树的层序遍历
题目描述
题目分析
xxxx这道题,题目是“二叉树的层序遍历”,首先我们提取一下题目和题目内容的关键词。“二叉树”、“层序遍历”、“每一层值分别存储到一个vector”
(可能不同的人看的着重点不完全相同,我注意到的是以上三个)。二叉树的层序遍历还是比较好搞的,根据数据结构的基础知识,只要我们借助一个队列,利用队列的“先进先出”的特性,就能够很好的进行层序遍历。为了避免部分读者暂时不会代码实现,影响后面的问题分析和代码阅读。所以我先讲解一下如何借助队列实现二叉树的层序遍历
xxxx如果有想对二叉树有更深更全面的了解和学习的读者可以打开下面的链接学习:二叉树的深入学习
二叉树的层序遍历
首先看一下动图,了解怎么叫层序遍历
xxxx层序遍历需要借助队列,首先将头结点入队,然后出队访问出队的结点,如果该出队的结点有左孩子则左孩子入队;如果有右孩子则右孩子入队。再循环,出队得到一个节点,然后访问出队的结点,如果该出队的结点有左孩子则左孩子入队;如果有右孩子则右孩子入队……知道队列为空,则遍历结束。
代码实现
//二叉树结点的定义
/**
* struct TreeNode
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* ;
*/
void SequenceTraversal(TreeNode* root)
queue<TreeNode*> q;
q.push(root)
while(q.size())
TreeNode node = q.front();
VisitNode(node);
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
xxxx明白了如何进行层序遍历,接下来我们继续进行本题的题目分析。
xxxx在“二叉树”、“层序遍历”、“每一层值分别存储到一个vector”这三个关键词中,我们已经解决了前两个关键词了,现在最重要的,也是我做这道题认为最困难的部分就是如何将每一层的数据分别存储。通过刚刚对层序遍历的认识,我们发现,他只能单一的存储数据,但是无法区分某一个属于第几层。因此就需要改进一下便于标识数据属于第几层。但是大体思路还是利用队列进行层序遍历。
xxxx我们发现在层序遍历的每个循环中,大体分为两个部分:1、处理一个结点。2、将被处理的结点的左右孩子入队
xxxx这就说明,我们在处理完一个结点后,就可以知道该结点有几个孩子。我们就可以将孩子的个数统计出来,这样我们处理一个孩子就将计数器-1,直到计数器为0,我么就知道了这个结点的孩子已经处理完成。
xxxx将一个结点扩展成一层结点。假设我们已知某一层有num个结点,由于层序遍历是一层一层遍历。于是当我们处理完这一层的num结点,计数器count就可以统计处这一层结点一共有几个孩子,孩子数量count就是下一层结点的个数。然后我们再把count赋值给num,这样就更新了下一层的结点个数,count就可以再次统计处下一层结点的孩子个数。这样一直循环,还是截止到队列为空,遍历结束。这样我们就能很好的知道每一层的结点个数。
代码实现
vector<vector<int> > levelOrder(TreeNode* root)
// write code here
if(root == nullptr)
return ;
vector<vector<int> > ret;
queue<TreeNode*> q;
//先将头结点入队
q.push(root);
//第一层只有头结点,所以num初始化为1
int num = 1;
//记录下一层结点数的计数器count初始化0
int count = 0;
//定义v,用于存储每一层的结果
vector<int> v;
while(q.size())
//先从队中取出对头数据
TreeNode* tmp = q.front();
//处理该结点,将val插入到v中
v.push_back(tmp->val);
//pop掉之后count就减1,说明这一层处理完一个数据了
q.pop();
num--;
//如果有左孩子,则入队
if(tmp->left)
q.push(tmp->left);
//count++,证明下一层结点数+1
count++;
//如果有右孩子,则入队
if(tmp->right)
q.push(tmp->right);
//count++,证明下一层结点数+1
count++;
//因为处理该层一个结点num-1,如果num==0,说明该层结点处理完毕,就要更新num,count
if(num==0)
//将该层的结果push到二维数组中
ret.push_back(v);
vector<int> a;
v = a;
//该处理下一层了,下一层结点数就是count
num = count;
//count重新置为0
count = 0;
//循环结束,就可以返回vector<vector<int>>这个二维数组了
return ret;
;
总结
xxxx这道题考查的本质就是二叉树的层序遍历,其实二叉树的层序遍历本身不是一个特别难的知识点,只要实现过一次,基本就能很好的实现层序遍历。所以如果这题,没有要求分别返回每一层的数据结果,是不可能到达一个中等难度的。困难点就在于如何控制每一层的开始和停止。如何知道什么时候一层结束。那我们利用的方面有:1、层序遍历,就是一层一层的遍历;2、对于每个结点,我们都可以直接访问他们的左右孩子进行计数。
xxxx这道题大体就是这样。如果有好的解题方法或者我的方法有什么瑕疵错误,请在评论区指出。让我们互相学习,共同进步。谢谢大家!
leetcode107.二叉树的层序遍历ii(代码片段)
给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树[3,9,20,null,null,15,7],3/\\920/\\157返回其自底向上的层序遍历为:[[15,7],... 查看详情
leetcode107.二叉树的层序遍历ii(代码片段)
给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树[3,9,20,null,null,15,7],3/\\920/\\157返回其自底向上的层序遍历为:[[15,7],... 查看详情
leetcode——二叉树的层序遍历(代码片段)
1.二叉树的层序遍历给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。2.题解解法一:BFS解决:广度优先搜索这题和剑指Offer32——从上到下打印二叉树其实是... 查看详情
刷题-力扣-102.二叉树的层序遍历(代码片段)
102.二叉树的层序遍历题目链接来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目描述给你一个二叉树,请你返回其... 查看详情
leetcode-二叉树的层序遍历-77(代码片段)
题目要求 给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。解析 广度优先搜索,入队出队代码实现classSolutionpublic:vector<vector<int>>levelOrder(TreeNode*... 查看详情
二叉树的层序遍历原理+leetcode真题练习(代码片段)
二叉树的层序遍历层序遍历是继前序、中序、后序遍历之后的第二类遍历方式。一、层序遍历假设二叉树根节点(root)所在层数为1,层序遍历就是从根节点出发,首先访问根节点,接着从左到右的访问第二层上的节点... 查看详情
leetcode刷题100天—107.二叉树的层序遍历ii(二叉树)—day08(代码片段)
前言:作者:神的孩子在歌唱大家好,我叫运智107.二叉树的层序遍历II难度中等473收藏分享切换为英文接收动态反馈给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所... 查看详情
leetcode刷题100天—102.二叉树的层序遍历(二叉树)—day09(代码片段)
前言:作者:神的孩子在歌唱大家好,我叫运智102.二叉树的层序遍历难度中等987收藏分享切换为英文接收动态反馈给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有... 查看详情
leetcode-102-二叉树的层序遍历
...。(即逐层地,从左到右访问所有节点)。示例说明请见LeetCode官网。来源:力扣(LeetCode)链接:https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解法一:利用队列遍历二叉... 查看详情
leetcode刷题python102.二叉树的层序遍历(代码片段)
1题目给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示例2:输入:root=[1]输出: 查看详情
leetcode0102.二叉树的层序遍历+针对c++的使用空间优化(可能不同于常规做法)(代码片段)
...xff08;可能不同于常规做法)力扣题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地 查看详情
二叉树的层序遍历(代码片段)
107.二叉树的层序遍历II给定一个二叉树,返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树[3,9,20,null,null,15,7],3 /\\920/\\157返回其自底... 查看详情
nc15二叉树的层序遍历(代码片段)
题目描述二叉树的层序遍历解题思路运用二叉树的层序遍历和二叉树的深度计算的思想;代码展示/***structTreeNode* intval;* structTreeNode*left;* structTreeNode*right;*;*/classSolutionpublic:/****@paramrootTreeNode类*@returnint整型vector 查看详情
java二叉树的层序遍历(代码片段)
#yyds干货盘点#leetcode-102.二叉树的层序遍历
借助队列的先进先出特性,将要遍历的节点放到队列里,实现层序遍历102.二叉树的层序遍历给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出... 查看详情
102.二叉树的层序遍历(队列+bfs+结构体)(代码片段)
题目描述leetcode-102:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/解题关键队列BFS结构体碎碎念这道题可以不用结构体,在while循环里面加一个for循环来遍历某一层的节点。但是很多宽搜的题一般节点需要存储一些别的信息... 查看详情
102.二叉树的层序遍历(代码片段)
二叉树的层序遍历给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。示例:二叉树:[3,9,20,null,null,15,7]3/920/157返回其层序遍历结果:[[3],[9,20],[15,7]]/***Defini... 查看详情
102.二叉树的层序遍历(代码片段)
/***Definitionforabinarytreenode.*structTreeNode*intval;*structTreeNode*left;*structTreeNode*right;*;*//***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesa 查看详情