class Solution {
public: vector> zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> result; int k=0;
return BFS(root,result,k);
}
vector<vector<int>> BFS(TreeNode *root,vector>&vec, int k){ // 广度优先算法不需要递归，很舒服
if(root==NULL)return vec; //这里的 &vec 引用不能少
queue<TreeNode*> que; //建立一个盛放节点指针的队列
que.push(root);
while(que.size()){
k+=1;
vector<int> level; //放置每层的节点开始前，都需要新建一个空的层容器来存放
int size=que.size(); //每一层的节点树在这里确定
for(int i=0;i<size;i++l);{ // 将每一层的节点都放入层容器中去
TreeNode *temp=que.front();
que.pop();
level.push_back(temp->val);
if(temp->right!=NULL)que.push(temp->right);
if(temp->left!=NULL)que.push(temp->left);
}
if(k%2!=0) reverse(level.begin(),level.end());
vec.push_back(level); //将放完层节点的层容器再放置到最终的结果容器中去
}
return vec;
}
};
