For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
问题描述：给定一个二叉树，返回它的层次遍历，要求相邻的两层的访问次序不一样，一层是从左到右，另外一层是从右到左。
之前做的关于层次遍历的采用的是队列，这样，每层都是同一个方向访问。在这里要求是相邻的两层的访问次序不一样。是否可以采用栈呢？比如这个例子，先访问根节点，
然后入栈，然后访问根节点的左孩子和右孩子，接着也入栈，再逐个出栈并访问右孩子，再访问左孩子，也依次入栈。
代码中使用了两个栈，一个栈的内容对应了一层，交替访问两个栈。
class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(root == NULL)
return vector >(0, vector());
stack sta1, sta2;
vector
> vec;
vector ivec;
TreeNode *pnode = NULL;
sta1.push(root);
ivec.push_back(root->val);
vec.push_back(ivec);
ivec.clear();
while(!sta1.empty()) {
while(!sta1.empty()) {
pnode = sta1.top();
sta1.pop();
if(pnode->right) {
sta2.push(pnode->right);
ivec.push_back(pnode->right->val);
}
if(pnode->left) {
sta2.push(pnode->left);
ivec.push_back(pnode->left->val);
}
}
if(!ivec.empty()) {
vec.push_back(ivec);
ivec.clear();
}
while(!sta2.empty()) {
pnode = sta2.top();
sta2.pop();
if(pnode->left) {
sta1.push(pnode->left);
ivec.push_back(pnode->left->val);
}
if(pnode->right) {
sta1.push(pnode->right);
ivec.push_back(pnode->right->val);
}
}
if(!ivec.empty()) {
vec.push_back(ivec);
ivec.clear();
}
}
return vec;
}
};