福田做网站公司怎么选,企业网络组建工作流程,东莞网站设计出名 乐云践新,家装品牌排行榜前十名创作不易#xff0c;本篇文章如果帮助到了你#xff0c;还请点赞 关注支持一下♡#x16966;)!! 主页专栏有更多知识#xff0c;如有疑问欢迎大家指正讨论#xff0c;共同进步#xff01; 更多算法知识专栏#xff1a;算法分析#x1f525; 给大家跳段街舞感谢… 创作不易本篇文章如果帮助到了你还请点赞 关注支持一下♡)!! 主页专栏有更多知识如有疑问欢迎大家指正讨论共同进步 更多算法知识专栏算法分析 给大家跳段街舞感谢支持ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ LeetCode题解专栏【LeetCode刷题笔记】 目录 题目链接一、题目描述二、示例三、题目分析四、代码实现C 题目链接
LeetCode 103. 二叉树的锯齿形层序遍历
一、题目描述
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
二、示例
示例 1 输入root [3,9,20,null,null,15,7] 输出[ [3],[20,9],[15,7] ]
三、题目分析
二叉树的层序遍历链接 【LeetCode刷题笔记】102. 二叉树的层序遍历
锯齿形层序遍历的解法基于普通的层序遍历基础上
二叉树的层序遍历使用队列将每层节点入队再根据该层数量queue.size()控制遍历
锯齿形层序遍历就是对层序遍历再多加个约束条件一层正常遍历一层将遍历后的结果插入到上个数据前面
反方向遍历实现方法将数据从队列弹出后每次添加到结果数组中添加的位置在前 就实现了从右向左输出 因此只需要控制哪一层正常遍历哪一层反方向遍历即可使用一个bool标记位每遍历一层后控制反向遍历
四、代码实现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 zigzagLevelOrder(TreeNode* root) {vectorvectorint res; //返回结果二维数组queueTreeNode* qe; //打印队列if(rootnullptr)return res;qe.push(root); //将根节点入队bool ji true; //控制遍历方向的标记位while(!qe.empty()) //是否还有节点未处理{int size qe.size(); //本层节点个数 用于控制本层 内循环vectorint level; //每层的打印结果for(int i0;isize;i){TreeNode* cur qe.front();if(ji){//正向遍历在数组尾部添加节点数据level.push_back(cur-val);qe.pop();}else{//反方向遍历将遍历后的结果插入到上个数据前面就实现了反向遍历level.insert(level.begin(),cur-val);qe.pop();}if(cur-left)qe.push(cur-left); //左孩子入队if(cur-right)qe.push(cur-right); //右孩子入队}ji!ji; //每层处理完后将标记位置为反res.push_back(level); //将每层结果放入二维数组结果中}return res; //返回二维数组结果}
};大家的点赞、收藏、关注将是我更新的最大动力 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大我会继续不断努力提供有价值的内容
如果本文哪里有错误的地方还请大家多多指出(●◡●)