Given a binary tree, write a method that traverses the tree in zigzag order (similar to level-order traversal but toggle left to right and right to left visiting of the nodes at each level).void ZigzagOrderTraversal(Node *n)
{
if (!n)
return;
bool toggle = true;
stack<Node*> lr; // Left to right
stack<Node*> rl; // Right to left
lr.push(n);
while (!lr.empty() || !rl.empty())
{
if (toggle)
{
while (!lr.empty())
{
n = lr.top();
lr.pop();
cout << n->value << " "; // Visit
if (n->left)
rl.push(n->left);
if (n->right)
rl.push(n->right);
}
toggle = toggle ^ true;
}
else
{
while (!rl.empty())
{
n = rl.top();
rl.pop();
cout << n->value << " "; // Visit
if (n->right)
lr.push(n->right);
if (n->left)
lr.push(n->left);
}
toggle = toggle ^ true;
}
}
} |