Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
本题还是树的层次遍历，但是稍微有点不一样，要求奇数层从左往右输出，偶数层从右往左输出。常规的层次遍历使用BFS实现，即队列，这里要求颠倒顺序，马上想到用堆栈。
维护一个left2right布尔变量，当tru时，把孩子从左往右压栈，这样下一层的输出顺序就是从右往左了；当为false时相反。这里我们还需要用到两个堆栈，分别保存当前层和下一层的结果。
talk is cheap, show you the code!
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode* root)
{
vector<vector<int> > ans;
if (!root)
return ans;
bool left2right = true;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
stack<TreeNode*> stk2;
vector<int> cand;
size_t n = stk.size();
for (size_t i = 0; i < n; ++i) {
TreeNode* top = stk.top();
stk.pop();
if (!top)
continue;
cand.push_back(top->val);
if (left2right) {
stk2.push(top->left);
stk2.push(top->right);
}
else {
stk2.push(top->right);
stk2.push(top->left);
}
}
left2right = !left2right;
if (!cand.empty())
ans.push_back(cand);
stk = stk2;
}
return ans;
}
};本代码提交AC，用时6MS。
二刷。不使用两个栈，而使用一个双端队列也可以：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == NULL)return ans;
deque<TreeNode*> q;
q.push_back(root);
bool left2right = true;
while (!q.empty()) {
vector<int> cur;
if (left2right) {
int n = q.size();
for (int i = 0; i < n; ++i) {
cur.push_back(q[i]->val);
}
ans.push_back(cur);
for (int i = n - 1; i >= 0; --i) {
TreeNode* tn = q.back();
q.pop_back();
if (tn->right)q.push_front(tn->right);
if (tn->left)q.push_front(tn->left);
}
left2right = false;
}
else {
int n = q.size();
for (int i = n - 1; i >= 0; --i) {
cur.push_back(q[i]->val);
}
ans.push_back(cur);
for (int i = 0; i < n; ++i) {
TreeNode* tn = q.front();
q.pop_front();
if (tn->left)q.push_back(tn->left);
if (tn->right)q.push_back(tn->right);
}
left2right = true;
}
}
return ans;
}
};本代码提交AC，用时4MS。