照明公司网站制作手机推广app
题目描述
题目链接103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -100 <= Node.val <= 100
思路解析
与层序遍历类似，值需要在偶数层将所取出的val值数组反转再存入答案数组中
利用一个队列进行每层的节点存储，当队列中有元素时，遍历该队列，取出val值并将该节点的左右子节点放入队列，最后弹出该节点
需要注意的是，在遍历队列的时候，判断语句不能是队列的empty函数。因为每个元素还会放入子节点，所以在遍历前应当创建一个int变量进行存当前队列大小，再用队列大小进行遍历
代码实现
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(root==nullptr)return {};int cnt = 1;//层数vector<vector<int>>ans;queue<TreeNode*>que;//记录每一层的节点que.push(root);//第一层节点while(que.size()){//当该层还有元素则进入循环vector<int>vec;//记录该层节点的val值int n=que.size();while(n--){//取出val值，从左至右放入下一层元素vec.push_back(que.front()->val);if(que.front()->left)que.push(que.front()->left);if(que.front()->right)que.push(que.front()->right);que.pop();}if(cnt%2==0)reverse(vec.begin(),vec.end());//如果该层为双数层，反转数组ans.push_back(vec);//把该层val值数组放入答案数组中cnt++;//该层处理完成后层数加一}return ans;}
};