My accepted python code with one queue. Why do we need two stacks if one queue will do?

• Hello. Similar to someone's question here, I use one queue and do BFS. I maintain the level of the node along with it so I simply do in place reversal of the list of the traversed nodes. This just means calling

if this_level > 0 and this_level%2==0: result[-1] = result[-1][::-1]

in Python. I haven't read the two stack solution yet because I want to solve the problem myself. But I need to be convinced why such an approach is preferable over straightforward(probably this approach comes to mind for most people as well?) BFS solution.

class Elem:
def __init__(self, node, level):
self.node  = node
self.level = level

class Solution:
# @param root, a tree node
# @return a list of lists of integers
def zigzagLevelOrder(self, root):
result = []
if not root: return []

q = collections.deque()
q.appendleft(Elem(root, 0))

prev_level = -1
while q:
elem = q.pop()
this_node, this_level = elem.node, elem.level

# record result
if this_level != prev_level:
# reverse prev list if this_level is even
if this_level > 0 and this_level%2==0:
result[-1] = result[-1][::-1]

result.append([this_node.val])
prev_level = this_level
else:
result[-1].append(this_node.val)

# push the children to the queue
if this_node.left != None:
q.appendleft(Elem(this_node.left, this_level+1))
if this_node.right != None:
q.appendleft(Elem(this_node.right, this_level+1))

if this_level>0 and this_level%2==1:
result[-1] = result[-1][::-1]

return result

• I'm attaching C++ version of the above solution as well. The algorithm is the same as above. Just written in C++. The running time is 244ms (Python) vs 36ms (C++).

class Elem {
public:
TreeNode* node;
int level;
Elem(TreeNode* _node, int _level){
node = _node;
level = _level;
}
};

class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> result;
if (root==NULL) return result;

queue<Elem> q;
q.push(Elem(root, 0));

int prev_level = -1, this_level = -1;

while (q.size() > 0){
Elem elem = q.front();
TreeNode* this_node = elem.node;
this_level = elem.level;
q.pop();

// push to the result.
if (this_level != prev_level){
// reverse prev level result if cur level is even
if (this_level >0 && this_level%2==0) reverse(result.back().begin(), result.back().end());
prev_level = this_level;
result.push_back(vector<int>(1,this_node->val));
} else {
result.back().push_back(this_node->val);
}

// push the children to the q
if (this_node->left != NULL) q.push(Elem(this_node->left, this_level+1));
if (this_node->right !=NULL) q.push(Elem(this_node->right, this_level+1));
}

if (this_level%2==1) reverse(result.back().begin(), result.back().end());
return result;
}
};

• to make C++ solution more concise

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> res;
if(!root)return res;

queue<TreeNode *> q;
q.push(root);
int cur=1,next=0;
bool flag=false;
vector<int> tmp;
while(!q.empty())
{
TreeNode *p=q.front();
q.pop();
tmp.push_back(p->val);
cur--;
if(p->left){q.push(p->left);next++;}
if(p->right){q.push(p->right);next++;}
if(cur==0)
{
if(flag)reverse(tmp.begin(),tmp.end());
res.push_back(tmp);
tmp.clear();
cur=next;
next=0;
flag=!flag;
}
}

return res;
}

• The reversal part will cause double time-overhead. Even your algorithm is also O(n), the time needed to perform traversal is twice as two-stack version.

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