leetcode103——二叉树的锯齿形层次遍历

 1 /*
 2  * @lc app=leetcode.cn id=103 lang=cpp
 3  *
 4  * [103] 二叉树的锯齿形层次遍历
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
15  * };
16  */
17 class Solution {
18 public:
19     //交替行的输出，考虑用一个flag标志位
20 
21     /*利用二叉树的层序遍历，然后用一个变量来记录树的深度（0、1、2...），
22     深度为偶数，从左向右添加这层的节点值；深度为奇数，从右向左添加这层的节点值。*/
23     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
24        if(!root) return {};   //vector为空时的返回值
25         vector<vector<int>> res;
26         queue<TreeNode*> q;
27         int flag=0;  // 标志位，判断哪一行翻转
28         q.push(root);
29 
30         while(!q.empty()){
31             vector<int> tmp;
32             int len=q.size();
33             for(int i=0;i<len;i++){
34                 TreeNode* node=q.front();
35                 q.pop();
36                 tmp.push_back(node->val);
37                 if(node->left) q.push(node->left);
38                 if(node->right) q.push(node->right);
39             }
40             if(flag%2==1) reverse(tmp.begin(),tmp.end());
41             flag++;
42             res.push_back(tmp);
43         }
44         return res;
45     }
46 };
47 // @lc code=end