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

题目描述

题目链接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;
    }
};