- Given a binary tree,
- return the zigzag level order traversal of its nodes ' values. (ie, from left to right, then right to left for the next level and alternate between).
- For example:
- Given binary tree{3,9,20,#,#,15,7},
- 3
- / |
- 9 20
- / |
- 15 7
- return its zigzag level order traversal as:
- [
- [3],
- [20,9],
- [15,7]
- ]'
思路:
在层序遍历的基础上, 修改进出队列的操作顺序
或者是按照层次的奇偶性来判断层次遍历的结果是否应该 reverse, 后面的思路编码实现较简单
下面是思路 1 的代码实现, 我们采用 deque 以得到更多的队列操作
- /**
- * Definition for binary tree
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- public: vector < vector < int > >zigzagLevelOrder(TreeNode * root) {
- vector < vector < int > >vv;
- if (root == NULL) return vv;
- deque < TreeNode * >q;
- TreeNode * temp = NULL;
- q.push_back(root);
- int cnt = 0;
- while (!q.empty()) {
- int len = q.size();
- vector < int > t;
- if (cnt % 2 == 0) {
- for (int i = 0; i < len; i++) {
- temp = q.front();
- q.pop_front();
- if (temp - >left) q.push_back(temp - >left);
- if (temp - >right) q.push_back(temp - >right);
- t.push_back(temp - >val);
- }
- } else {
- for (int i = 0; i < len; i++) {
- temp = q.back();
- q.pop_back();
- if (temp - >right) q.push_front(temp - >right);
- if (temp - >left) q.push_front(temp - >left);
- t.push_back(temp - >val);
- }
- }
- vv.push_back(t);
- cnt++;
- }
- return vv;
- }
- };
下面是思路二的代码:
- /**
- * Definition for binary tree
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- public: vector < vector < int > >zigzagLevelOrder(TreeNode * root) {
- vector < vector < int > >vv;
- if (root == NULL) return vv;
- queue < TreeNode * >q;
- TreeNode * temp = NULL;
- q.push(root);
- int cnt = 1;
- while (!q.empty()) {
- int len = q.size();
- vector < int > t;
- for (int i = 0; i < len; i++) {
- temp = q.front();
- q.pop();
- if (temp - >left) q.push(temp - >left);
- if (temp - >right) q.push(temp - >right);
- t.push_back(temp - >val);
- }
- if (cnt % 2 == 0) reverse(t.begin(), t.end());
- vv.push_back(t);
- cnt++;
- }
- return vv;
- }
- };
来源: http://www.jianshu.com/p/0231a080ce25