LeetCode103. Binary Tree Zigzag Level Order Traversal题解
2017-03-22 09:55:33         来源：SYSU_LBY的博客

## 1. 题目描述

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).

## 2. 样例

Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

## 3. 分析

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > zigzagLevelOrder(TreeNode* root) {
vector >result;
vector everyLevel;
queuenode;
queuelevel;
int current_level = 0;
int last_level = 0;
TreeNode *current_node = root;
if (root != NULL) {
node.push(current_node);
level.push(current_level);
while(!node.empty()) {
current_level = level.front();
current_node = node.front();
level.pop();
node.pop();
if (current_level > last_level) {
last_level = current_level;
if (current_level % 2 == 0) {
reverse(everyLevel.begin(), everyLevel.end());
}
result.push_back(everyLevel);
everyLevel.clear();
everyLevel.push_back(current_node->val);
}
else {
everyLevel.push_back(current_node->val);
}
if (current_node->left != NULL) {
node.push(current_node->left);
level.push(current_level+1);
}
if (current_node->right != NULL) {
node.push(current_node->right);
level.push(current_level+1);
}
}
if (current_level % 2 != 0) {
reverse(everyLevel.begin(), everyLevel.end());
}
result.push_back(everyLevel);
}
return result;
}
};```