Clear C++ Iterative Solution with 2 Stack

• Use 2 stacks, one for the current level, one for the next level.
• If current level is even then push the children to the stack by left-to-right order.
• If current level is odd then push the children to the stack by right-to-left order.

Here is the solution:

``````vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> > ret;
vector<int> sub;
stack<TreeNode*> s[2];
int lvl = 0;

if (root == NULL)
return ret;

s[lvl].push(root);

while(!s[0].empty() || !s[1].empty()) {
while(!s[lvl].empty()) {
TreeNode *node = s[lvl].top();
s[lvl].pop();

if (node == NULL) continue;

sub.push_back(node->val);
if (lvl % 2 == 0) {
s[(lvl + 1) % 2].push(node->left);
s[(lvl + 1) % 2].push(node->right);
}
else {
s[(lvl + 1) % 2].push(node->right);
s[(lvl + 1) % 2].push(node->left);
}
}
if (sub.size() > 0)
ret.push_back(sub);
sub.clear();

lvl = (lvl + 1) % 2;
}
return ret;
}``````

• Similar Idea as you.

``````/**
* Definition for binary tree
* 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> > res;
if (root == NULL)
return res;

stack<TreeNode*> nodes;
nodes.push(root);
bool left_to_right = true;
while (!nodes.empty()) {
stack<TreeNode*> next_nodes;
vector<int> cur_values;
while (!nodes.empty()) {
TreeNode *cur_node = nodes.top();
nodes.pop();
if (cur_node == NULL)
continue;
cur_values.push_back(cur_node->val);
if (left_to_right) {
next_nodes.push(cur_node->left);
next_nodes.push(cur_node->right);
} else {
next_nodes.push(cur_node->right);
next_nodes.push(cur_node->left);
}
}
if (!cur_values.empty())
res.push_back(cur_values);
nodes = next_nodes;
left_to_right = !left_to_right;
}
return res;
}
};``````

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