在做题中学习（91）：二叉树的锯齿形层序遍历

解法：队列 + 模拟

思路：用队列模拟，先让头结点入队列，入ret结果集，在队列不为空时，取队列中每一个元素进行左右孩子的入队列，并且同层节点的左右孩子都入完毕之后，才能加入tmp结果集并进入下一层。发现偶数层数对应的一组节点锯齿形遍历时需要逆序，因此还需要一个变量记录当前的层数,如果是偶数层需要让tmp结果集逆序后再加入ret中。

附上完整代码：

class Solution 
{
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(root == nullptr)return {};vector<vector<int>> ret;queue<TreeNode*> q;ret.push_back({root->val});q.push(root);int count = 1;while(!q.empty()){int sz = q.size();vector<int> r;for(int i = 0;i<sz;i++){TreeNode* tmp = q.front(); q.pop();if(tmp->left){r.push_back(tmp->left->val);q.push(tmp->left);}if(tmp->right){r.push_back(tmp->right->val);q.push(tmp->right);}}count++;if(count % 2 == 0)reverse(r.begin(),r.end());if(r.size())ret.push_back(r);}        return ret;}
};