【树】103. 二叉树的锯齿形层次遍历

 1 //小集合和大集合均OK
 2 class Solution {
 3 public:
 4     vector<vector<int> > zigzagLevelOrder(TreeNode *root)
 5     {
 6         vector< vector<int> > result;
 7         if (root == NULL)
 8         {
 9             return result;
10         }
11         
12         queue<TreeNode*> q;
13         q.push(root);
14         
15         vector<int> tmp(0);
16         
17         int count = 1;
18         int level = 0;
19         
20         int flag = 1; //标志
21         while(!q.empty())
22         {
23             tmp.clear();
24             level = 0;
25             
26             for (int i = 0; i < count; ++i)
27             {
28                 root = q.front();
29                 q.pop();
30                 tmp.push_back(root->val);
31                 
32                 if (root->left != NULL)
33                 {
34                     q.push(root->left);
35                     ++level;
36                 }
37                 if (root->right != NULL)
38                 {
39                     q.push(root->right);
40                     ++level;
41                 }
42             }
43             count = level;
44             
45             if(flag % 2 == 0)
46             {
47                 reverse(tmp.begin(), tmp.end());
48             }
49             flag++;
50             
51             result.push_back(tmp);
52         }
53         //reverse(result.begin(), result.end());
54         return result;
55     }
56 };