【LeetCode刷题笔记】103.二叉树的锯齿形层序遍历

创作不易，本篇文章如果帮助到了你，还请点赞 关注支持一下♡>𖥦<)!! 主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！ 更多算法知识专栏：算法分析🔥 给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

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: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> res; //返回结果：二维数组 queue<TreeNode*> qe; //打印队列 if(root==nullptr)return res; qe.push(root); //将根节点入队 bool ji = true; //控制遍历方向的标记位 while(!qe.empty()) //是否还有节点未处理 { int size = qe.size(); //本层节点个数 用于控制本层 内循环 vector<int> level; //每层的打印结果 for(int i=0;i<size;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; //返回二维数组结果 } };

---

大家的点赞、收藏、关注将是我更新的最大动力！ 欢迎留言或私信建议或问题。 大家的支持和反馈对我来说意义重大，我会继续不断努力提供有价值的内容！ 如果本文哪里有错误的地方还请大家多多指出(●'◡'●)