# Two stack algorithm

• Use two stacks, pushing the nodes of the tree in difference sequence to the stack. For the level visiting from left to right, we push its sub tree by the left--right child order. For the right to left, we push its child by right-left order.

``````   vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if(!root)
return result;
stack<TreeNode*> S;
S.push(root);
stack<TreeNode*> T;
vector<int> level;
TreeNode* temp = NULL;

while(!S.empty() || !T.empty()){
while(!S.empty()){
temp = S.top();
S.pop();
level.push_back(temp->val);
if(temp->left){
T.push(temp->left);
}
if(temp->right){
T.push(temp->right);
}
}
if(level.size()){//one level is done
result.push_back(level);
level.clear();
}

while(!T.empty()){
temp = T.top();
T.pop();
level.push_back(temp->val);
if(temp->right){
S.push(temp->right);
}
if(temp->left){
S.push(temp->left);
}
}
if(level.size()){
result.push_back(level);
level.clear();
}
}
//return the result;
return result;
}``````

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