问题描述:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TP35ENrRkT3VFROBDOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL4kjM2EDNxEjM5IjMwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
问题解析:
本题与102题解决的方法类似,只是我们改用队列的结构来进行求解。首先队列是一种先进先出的数据结构,而且对于数据的接入采用q.push()函数,而对于数据的输出我们采用q.pop()函数。每一次迭代过程,我们都需要把左右节点压入队列中,并且保证压入的数据不会出现比队列长度更长的情况。还要对于偶数行,进行tmp数据反转情况,然后再压入到数组集中。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> q; //定义队列的数据结构
q.push(root); //将树根节点加入队列中,先进先出原则
int x=0; //判断当前行数的奇数偶数
while(!q.empty())
{
int l = q.size(); //计算队列的长度
vector<int> tmp;
for(int i=0;i<l;i++)
{
TreeNode* t=q.front(); //让t指向队头
q.pop();
tmp.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
x++;
if(x%2==0) reverse(tmp.begin(),tmp.end()); //如果是偶数行(从第1行开始),需要tmp数组反转
res.push_back(tmp);
}
return res;
}
};