网站设计岗位做哪些事情,搜索引擎网站优化和推广方案,中小型企业网络拓扑图及配置,辽阳化工网站建设创作不易#xff0c;本篇文章如果帮助到了你#xff0c;还请点赞 关注支持一下♡#x16966;)!! 主页专栏有更多知识#xff0c;如有疑问欢迎大家指正讨论#xff0c;共同进步#xff01; 更多算法知识专栏#xff1a;算法分析#x1f525; 给大家跳段街舞感谢… 创作不易本篇文章如果帮助到了你还请点赞 关注支持一下♡)!! 主页专栏有更多知识如有疑问欢迎大家指正讨论共同进步 更多算法知识专栏算法分析 给大家跳段街舞感谢支持ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ LeetCode题解专栏【LeetCode刷题笔记】 目录 题目链接一、题目描述二、示例三、题目分析四、代码实现C 题目链接
102. 二叉树的层序遍历
一、题目描述
给你二叉树的根节点root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
二、示例
示例 1
输入root [3,9,20,null,null,15,7] 输出[ [3],[9,20],[15,7] ]
示例 2
输入root [1] 输出[ [1] ] 示例 3
输入root [ ] 输出[ ]
三、题目分析
要按照每层向下遍历就需要知道每层节点的数量用于控制每次输出几个数据再进入下一层
与深度遍历不同的是在左子树遍历时需要记住当前层的右子树仍未遍历。
难点在于控制左右子树非兄弟节点也按层输出例如下图中的6、12、15、7需要在同一层输出而深入9遍历6和12的时候15和7就不会被遍历到
问题转化为如何保存同层仍未遍历的节点或者说 遍历同层节点时如何保存同层非兄弟节点的孩子节点
如果说深度遍历的递归借助了栈先进后出的特性二叉树的层序遍历就需要先进先出的队列
先将根节点放入队列再输出队列头根节点的数据再判断根节点是否存在左右子节点如果存在就将其入队。
这样从根节点开始每次遍历1个节点时同时将其左右孩子节点放入队列再按照每层数量从队列中取出每层数据
每次出队时都进行相同的操作就实现了按层遍历。 四、代码实现C
/*** 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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint res; //返回结果二维数组if(rootnullptr)return res;queueTreeNode* qe; //打印队列qe.push(root); //将根节点入队while(!qe.empty()) //是否还有节点未处理{vectorint level; //每层的打印结果int size qe.size(); //每层节点数量for(int i0;isize;i){TreeNode* cur qe.front(); //获取队列头level.push_back(cur-val); //打印节点数据if(cur-left)qe.push(cur-left); //左孩子入队if(cur-right)qe.push(cur-right); //右孩子入队qe.pop(); //弹出}res.push_back(level); //将每层结果放入二维数组结果中}return res;}
};大家的点赞、收藏、关注将是我更新的最大动力 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大我会继续不断努力提供有价值的内容
如果本文哪里有错误的地方还请大家多多指出(●◡●)
