双端队列层序打印二叉树－－奇层从左到右，偶层从右到左

 1 vector<vector<int>> levelOrder(TreeNode* root){
 2 vector<vector<int>> res;
 3 if(root==NULL)   return res;
 4 bool flag = true;//true--输出奇层，放入偶层（左右）－（前出后进）false--输出偶层，放入奇层（右左）－（后出前放）
 5 
 6 deque<TreeNode*> q;
 7 q.push_back(root);//第一层已经入队
 8 
 9 while(!q.empty()){
10 int n = q.size();
11 vector<int> out;
12 TreeNode* node;
13 
14 while(n>0){
15 if(flag){//前取后放：第一层为奇数
16 node = q.front();
17 q.pop_front();
18 if(node->left)
19 q.push_back(node->left);//放入下一层－－偶数层：后放－－左右
20 if(node->right)
21 q.push_back(node->right)
22 }
23 else{//后取前放：该层为偶层－－后取
24 node = q,back();
25 q.pop_back();
26 if(node->right)
27 q.push_front(node->right);//放入下一层－－奇层
28 if(node->left)
29 q.push_front(node->left;
30 }
31 out.push_back(node->val);
32 n--;
33 }
34 flag = !flag;
35 res.push_back(out);
36 }
37 return res;
38 }