力扣103.二叉树的锯齿形层序遍历

题目描述

题目链接103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间瓜代进行）。
示例 1：

1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
2. <strong>输出：</strong>[[3],[20,9],[15,7]]

复制代码

示例 2：

1. <strong>输入：</strong>root = [1]
2. <strong>输出：</strong>[[1]]

复制代码

示例 3：

1. <strong>输入：</strong>root = []
2. <strong>输出：</strong>[]

复制代码

提示：

• 树中节点数量在范围 [0, 2000] 内
  
• -100 <= Node.val <= 100
  

思路解析

        与层序遍历雷同，值必要在偶数层将所取出的val值数组反转再存入答案数组中
        利用一个队列进行每层的节点存储，当队列中有元素时，遍历该队列，取出val值并将该节点的左右子节点放入队列，末了弹出该节点
        必要注意的是，在遍历队列的时候，判断语句不能是队列的empty函数。由于每个元素还会放入子节点，以是在遍历前应当创建一个int变量进行存当前队列巨细，再用队列巨细进行遍历
代码实现

1. class Solution {
2. public:
3.     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
4.         if(root==nullptr)return {};
5.         int cnt = 1;//层数
6.         vector<vector<int>>ans;
7.         queue<TreeNode*>que;//记录每一层的节点
8.         que.push(root);//第一层节点
9.         while(que.size()){//当该层还有元素则进入循环
10.             vector<int>vec;//记录该层节点的val值
11.             int n=que.size();
12.             while(n--){//取出val值，从左至右放入下一层元素
13.                 vec.push_back(que.front()->val);
14.                 if(que.front()->left)que.push(que.front()->left);
15.                 if(que.front()->right)que.push(que.front()->right);
16.                 que.pop();
17.             }
18.             if(cnt%2==0)reverse(vec.begin(),vec.end());//如果该层为双数层，反转数组
19.             ans.push_back(vec);//把该层val值数组放入答案数组中
20.             cnt++;//该层处理完成后层数加一
21.         }
22.         return ans;
23.     }
24. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。