[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},

return its zigzag level order traversal as:

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

用BFS然后根据层数来判断是否要反转列表

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 
11 struct Node
12 {
13     TreeNode *node;
14     int level;
15     Node(){}
16     Node(TreeNode *n, int l):node(n), level(l){}
17 };
18 
19 class Solution {
20 private:
21     vector<vector<int> > ret;
22 public:
23     vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
24         // Start typing your C/C++ solution below
25         // DO NOT write int main() function
26         ret.clear();
27         
28         if (root == NULL)
29             return ret;
30         
31         queue<Node> q;
32         
33         q.push(Node(root, 0));
34         
35         int curLevel = -1;
36         
37         vector<int> a;
38         
39         while(!q.empty())
40         {
41             Node node = q.front();
42             
43             if (node.node->left)
44                 q.push(Node(node.node->left, node.level + 1));
45             
46             if (node.node->right)
47                 q.push(Node(node.node->right, node.level + 1));
48                 
49             if (curLevel != node.level)
50             {
51                 if (curLevel != -1)
52                 {
53                     if (curLevel % 2 == 1)
54                         reverse(a.begin(), a.end());
55                         
56                     ret.push_back(a);
57                 }
58                 a.clear();
59                 curLevel = node.level;
60             }
61             a.push_back(node.node->val);
62             q.pop();
63         }
64         
65         if (curLevel % 2 == 1)
66             reverse(a.begin(), a.end());
67             
68         ret.push_back(a);
69         
70         return ret;
71     }
72 };