# [leetcode] Binary Tree Zigzag Level Order Traversal

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,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

```[
[3],
[20,9],
[15,7]
]
```

confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//和前一题，lever order traversal相似，不同的是需要一个isReverse的boolean型变量来记录是否要反转当前的层的节点。
//翻转的话就insert到首位，不翻转的话就push_back
//lastNode用来记录当前层的最后一个节点，用来确定是否遍历到了新的层。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
queue<TreeNode *> q;
vector<vector<int > > re;
vector<int> thisRe;
bool isReverse = false;
if(root == NULL){
return re;
}
q.push(root);
TreeNode * lastNode = root;
while(!q.empty()){
TreeNode * p = q.front();
q.pop();
if(isReverse == false){
thisRe.push_back(p->val);
}
else{
thisRe.insert(thisRe.begin(), p->val);
}
if(p->left){
q.push(p->left);
}
if(p->right){
q.push(p->right);
}
if(p == lastNode){
re.push_back(thisRe);
thisRe.clear();
isReverse = isReverse == true?false:true;
if(!q.empty()){
lastNode = q.back();
}
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.