# Easy C++ BFS solution

• ``````class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
queue<TreeNode * > que;
queue<int> ique;
vector<vector<int>> ret;
que.push(root),ique.push(0);
while(!que.empty())
{
int lv = ique.front();ique.pop();
root = que.front();que.pop();
if(root)
{
if(ret.size() <= lv)
ret.push_back(vector<int>());
ret[lv].push_back(root->val);
ique.push(lv+1);ique.push(lv+1);
que.push(root->left);que.push(root->right);
}
}
for(int i = 0; i < ret.size(); i++)
if(i&1) reverse(ret[i].begin(),ret[i].end());
return ret;
}
};``````

• ``````/**
``````
• 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>> v1;
vector<int> c;
if(root==NULL)
return v1;
stack<TreeNode*> s1;
stack<TreeNode*> s2;

`````` s1.push(root);
while(!s1.empty() || !s2.empty())
{
while(!s1.empty())
{
root=s1.top();
s1.pop();
c.push_back(root->val);
if(root->left)
s2.push(root->left);
if(root->right)
s2.push(root->right);
``````
``````        }
if(c.size()>0)
v1.push_back(c);
c.clear();
while(!s2.empty())
{
root=s2.top();
s2.pop();
c.push_back(root->val);
if(root->right)
s1.push(root->right);
if(root->left)
s1.push(root->left);
}
if(c.size()>0)
v1.push_back(c);
c.clear();
}
return v1;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.