摘要：二叉树层序遍历每一层值分别存储到一个可能不同的人看的着重点不完全相同，我注意到的是以上三个。二叉树的层序遍历还是比较好搞的，根据数据结构的基础知识，只要我们借助一个队列，利用队列的先进先出的特性，就能够很好的进行层序遍历。
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>这个二维数组了 return ret; }};xxxx这道题考查的本质就是二叉树的层序遍历，其实二叉树的层序遍历本身不是一个特别难的知识点，只要实现过一次，基本就能很好的实现层序遍历。所以如果这题，没有要求分别返回每一层的数据结果，是不可能到达一个中等难度的。困难点就在于如何控制每一层的开始和停止。如何知道什么时候一层结束。那我们利用的方面有：1、层序遍历，就是一层一层的遍历；2、对于每个结点，我们都可以直接访问他们的左右孩子进行计数。
xxxx这道题大体就是这样。如果有好的解题方法或者我的方法有什么瑕疵错误，请在评论区指出。让我们互相学习，共同进步。谢谢大家！
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119516.html
分门别类刷算法，坚持，进步！ 刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们 收藏一下。 二叉树基础 二叉树是一种比较常见的数据结构，在开始刷二叉树...
摘要：题目给定一个二叉树，返回其节点值的锯齿形层次遍历。例如给定二叉树返回锯齿形层次遍历如下题解这道题要求用字型就是要求知道深度。稍作改动的是需要在遍历左子树和右子树的时候带上深度的信息，才能知道是加在列表头还是列表尾部。 题目 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如：给定二叉树 [3,9,20,null...
摘要：递归解法由于层次遍历的递归解法不是主流，因此只介绍前三种的递归解法前序遍历递归递归中序遍历递归递归后序遍历递归递归三种递归遍历的总结递归终止的条件为碰到空节点。 目录 分析二叉树的前序，中序，后序的遍历步骤 1.层序遍历 方法一：广度优先搜索 (以下解释来自leetcode官方题解) 方法...
摘要：题目给定一个二叉树，返回其按层次遍历的节点值。例如给定二叉树返回其层次遍历结果题解我们数据结构的书上教的层序遍历就是利用一个队列不断的把左子树和右子树入队。 题目 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 ...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
阅读 334·2023-04-26 02:59
阅读 531·2023-04-25 16:02
阅读 485·2021-09-08 09:36
阅读 1999·2021-08-05 09:55
阅读 3267·2019-08-30 15:55
阅读 4234·2019-08-30 15:44
阅读 1695·2019-08-30 13:02
阅读 2081·2019-08-29 16:57
