lintcode 二叉树的锯齿形层次遍历

二叉树的锯齿形层次遍历

描述：

给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

您在真实的面试中是否遇到过这个题？

Yes

样例

给出一棵二叉树 {3,9,20,#,#,15,7},

返回其锯齿形的层次遍历为：

[
  [3],
  [20,9],
  [15,7]
]
代码
（不知道为什么vector中的翻转reverse用不了，提交时会出现编译错误
In file included from /code/Main.cpp:23:0:
/code/Solution.cpp: In member function 'std::vector<std::vector > Solution::zigzagLevelOrder(TreeNode*)':
/code/Solution.cpp:30:22: error: 'class std::vector' has no member named 'reverse'
base.reverse(base.begin(), base.end()); 
）

 1 class Solution {
 2 public:
 3     /*
 4      * @param root: A Tree
 5      * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
 6      */
 7     vector<vector<int>> zigzagLevelOrder(TreeNode * root) {
 8         // write your code here
 9         vector<vector<int>> res;
10         if (root == NULL) return res;
11         bool flag = false;
12         queue<TreeNode*> que;
13         que.push(root);
14 
15         while (!que.empty()) {
16             int count = que.size();
17             vector<int> base;
18             while (count--) {
19                 TreeNode *temp = que.front();
20                 que.pop();
21                 base.push_back(temp->val);
22                 if (temp->left) {
23                     que.push(temp->left);
24                 }
25                 if (temp->right) {
26                     que.push(temp->right);
27                 }
28             }
29             if (flag) {
30                 vector<int> t;
31                 for (int i = base.size() - 1; i >= 0; i--) {
32                     t.push_back(base[i]);
33                 }
34                 res.push_back(t);
35             } else {
36                 res.push_back(base);
37             }
38             flag = !flag;
39         }
40         return res;
41     }
42 };

lintcode 二叉树的锯齿形层次遍历

二叉树的锯齿形层次遍历

相关推荐