# Accepted C++ Non-recursion Solution with One Queue and One Loop

• ``````class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> ret;
if(root == NULL) return ret;
vector<int> level;
bool tag = true;    //define the order of output(left to right or right to left)

queue<TreeNode*> TreeQ;
TreeQ.push(root);
TreeQ.push(NULL);   //distinguish one level from another level

while(!TreeQ.empty())
{
TreeNode* node = TreeQ.front();
TreeQ.pop();
if(node != NULL)
{
level.push_back(node->val);
if(node->left) TreeQ.push(node->left);
if(node->right) TreeQ.push(node->right);
}
else
{
if(tag)
{
ret.push_back(level);
}
else
{
reverse(level.begin(), level.end());
ret.push_back(level);
}
tag = !tag;
if(!TreeQ.empty())   // avoid endless loop to last level of tree
{
level.clear();
TreeQ.push(NULL);
}
}
}

return ret;
}
};
``````

I used two tricks:

1. Insert "NULL" to distinguish one level from another level

2. used one tag to define the order of output , meaning from left to right or right to left.

• In term of clarity, do you think if using 2 list is better than 1 list? if it is, below is the java solution:

``````public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
boolean fromLeft = true;

List<List<Integer>> results = new ArrayList<List<Integer>>();
if(root == null) return results;

ArrayList<TreeNode> l1 = new ArrayList<TreeNode>();
ArrayList<TreeNode> l2;

while(!l1.isEmpty()){
int z = l1.size();
l2 = new ArrayList<TreeNode>();
List<Integer> r = new ArrayList<Integer>();
TreeNode n;
for(int i=0; i<z; i++){
n = l1.get(i);
if(fromLeft){
}else {