[剑指Offer] 59.按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

【思路】先按层次遍历存入，通过设立标志位，将偶数层翻转。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution
12 {
13 public:
14     vector<vector<int> > Print(TreeNode* pRoot)
15     {
16         vector<vector<int> > res;
17         if(pRoot == NULL)
18             return res;
19         queue<TreeNode*> Que;
20         Que.push(pRoot);
21         bool flag = false;
22         while(!Que.empty())
23         {
24             vector<int> vec;
25             int size = Que.size();
26             for(int i = 0; i < size; i ++)
27             {
28                 TreeNode* temp = Que.front();
29                 vec.push_back(temp->val);
30                 if(temp->left)
31                     Que.push(temp->left);
32                 if(temp->right)
33                     Que.push(temp->right);
34                 Que.pop();
35             }
36             if(flag)
37                 std::reverse(vec.begin(),vec.end());
38             flag = !flag;
39             res.push_back(vec);
40         }
41         return res;
42     }
43 
44 };