# [c++] 5ms version: one queue and without reverse operation by using size of each level

• Assuming after traversing the 1st level, nodes in queue are {9, 20, 8}, And we are going to traverse 2nd level, which is even line and should print value from right to left [8, 20, 9].

We know there are 3 nodes in current queue, so the vector for this level in final result should be of size 3.
Then, queue [i] -> goes to -> vector[queue.size() - 1 - i]
i.e. the ith node in current queue should be placed in (queue.size() - 1 - i) position in vector for that line.

For example, for node(9), it's index in queue is 0, so its index in vector should be (3-1-0) = 2.

``````vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
if (root == NULL) {
return vector<vector<int> > ();
}
vector<vector<int> > result;

queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
bool leftToRight = true;

while ( !nodesQueue.empty()) {
int size = nodesQueue.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();

// find position to fill node's value
int index = (leftToRight) ? i : (size - 1 - i);

row[index] = node->val;
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}
// after this level
leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}``````

• I think use deque maybe more intuitive, no reverse too.

for zig, popback, pushfront, left then right,

for zag, popfront, pushback, right then left

[clear iterative solution with deque, no reverse][1]
[1]: https://leetcode.com/discuss/50994/clear-iterative-solution-with-deque-no-reverse

• deque is a pain to use

• how it hurt? performance? or?

• I think it is hard to write the code without errors when using deque

• I thought deque is intuitive, but not really such helpful. Still need judge reverse or not, right? Is any better way to use deque? ....

``````vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
deque<TreeNode*> doubleEndQueue;
if(root)  doubleEndQueue.push_back(root);
bool reverse = false;
vector<vector<int>> zigzagResult;
while(!doubleEndQueue.empty()){
int size = doubleEndQueue.size();
zigzagResult.push_back(vector<int>());
for(int i=0; i<size; i++){
if(!reverse){
auto node = doubleEndQueue.front();
zigzagResult.back().push_back(node->val);
doubleEndQueue.pop_front();
if(node->left)  doubleEndQueue.push_back(node->left);
if(node->right)  doubleEndQueue.push_back(node->right);
}
else{
auto node = doubleEndQueue.back();
zigzagResult.back().push_back(node->val);
doubleEndQueue.pop_back();
if(node->right)  doubleEndQueue.push_front(node->right);
if(node->left)  doubleEndQueue.push_front(node->left);
}

}
reverse = !reverse;
}
return zigzagResult;
}
``````

If only queue, with hint from StevenCooks, code is shorter.

`````` vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
queue<TreeNode*> q;
if(root)  q.push(root);
bool reverse = false;
vector<vector<int>> zigzagResult;
while(!q.empty()){
int size = q.size();
zigzagResult.push_back(vector<int>(size));
for(int i=0; i<size; i++){
int index = (reverse) ? size-i-1 : i;
zigzagResult.back()[index] = q.front()->val;
if(q.front()->left)  q.push(q.front()->left);
if(q.front()->right)  q.push(q.front()->right);
q.pop();
}
reverse = !reverse;
}
return zigzagResult;
}``````

• your idea is beautiful. I like the symmetry in your idea. left<-->right switched, deque front<---> back switched.

• Thanks so much for your code. I had a similar idea but I lost it when I was coding. Lol

• Java solution

`````` public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if(root == null){
return ret;
}
que.offer(root);
boolean flag = true;
while(!que.isEmpty()){
ArrayList<Integer> levelnode = new ArrayList<>();
int len  = que.size();
for(int i = 0; i < len; i++){
TreeNode temp = que.poll();
if(flag){
}else{
}
if(temp.left != null) que.offer(temp.left);
if(temp.right != null) que.offer(temp.right);
}
flag = !flag;
}
return ret;
}
``````

• @joy_zhou : I think this solution is terrible.

• ? i : (size - 1 - i);

Really like you idea of obtaining the insertion index.

• My python version.

``````from collections import deque
class Solution(object):
def zigzagLevelOrder(self, root):
if not root: return []
queue = deque()
queue.appendleft(root)
res = []
l2r = True
while queue:
size = len(queue)
tmp = [0]*size
for i in range(size):
node = queue.pop()
index = i if l2r else size-i-1
tmp[index] = node.val
map(lambda x: queue.appendleft(x), [x for x in [node.left, node.right] if x])
res.append(tmp)
l2r = not l2r
return res
``````

• ``````vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> allres;
queue<TreeNode*> q;

if(root==nullptr)
return allres;

bool isInOrder=true;
q.push(root);

while(!q.empty()) {
vector<int> res;

if(isInOrder) {
int start=0,end=q.size();
while(start<end) {
TreeNode* current=q.front();
q.pop();
res.push_back(current->val);
if(current->right!=nullptr)
q.push(current->right);
if(current->left!=nullptr)
q.push(current->left);
// allres.push_back(res);
start++;

}

allres.push_back(res);
isInOrder=!isInOrder;
}

else {
int start=0,end=q.size();
while(start<end) {
TreeNode* current=q.front();
q.pop();

res.push_back(current->val);

if(current->left!=nullptr)
q.push(current->left);
if(current->right!=nullptr)
q.push(current->right);

start++;
}
allres.push_back(res);
isInOrder=!isInOrder;
}

}

return allres;

}
``````

testcae: [1,2,3,4,null,null,5]
true: [[1],[3,2],[4,5]]
wrong:[[1],[3,2],[5,4]]

why is the result wrong ?who can know the wrong position??

• it is truly a good way to solve this problem

• Same idea, use BFS, written in java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
int flag = 1;

while (!que.isEmpty()) {
int size = que.size();
ArrayList<Integer> tmp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curr = que.poll();

if (curr.left != null) {
}
if (curr.right != null) {
}
}
if (flag == 1) {
} else if (flag == 0) {
Collections.reverse(tmp);
}

flag = (flag + 1) % 2;
}
return res;
}
}

``````

• I guess use list we can have better performance than deque, am I right?

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