二叉树的锯齿形层序遍历

给你二叉树的根节点root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

提示：

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

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

这题在剑指offer里面刷过捏，所以我啪地一下就写完了

简单来说就是个层序遍历的变种，要点有：

• 通过队列当前size来得知当前层有多少个节点
• 根据当前层节点数预先申请相应大小的数组
• 将申请好的数组放入答案中，根据答案中的数组个数判断当前层数
• 如果是奇数层，从前往后填；否则从后往前填

记得层数是从1开始计数的啊，当时就忘记这茬美美越界还愣了半天不知道错哪了

（感觉那个判断当前层数的方法比较巧妙，可以留意一下~

/**
 * 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>> ans;
        if(root == nullptr){
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int sz = q.size();
            vector<int> temp(sz, 0);
            ans.push_back(temp);
            int n = ans.size();
            for(int i = 0; i < sz; ++i){
                TreeNode* node = q.front();
                q.pop();
                if(n & 1){
                    ans[n - 1][i] = node->val;
                }else{
                    ans[n - 1][sz - i - 1] = node->val;
                }
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
        }
        return ans;
    }
};