[LeetCode] Binary Tree Zigzag Level Order Traversal

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},

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路：用空指针标记一层结束，用bool变量标记访问的是奇数层还是偶数层。
　　　时间复杂度O(n),空间复杂度O(1)
相关题目：《剑指offer》面试题61

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
13         vector<vector<int> > ret;
14         if (root == nullptr) return ret;
15         
16         vector<int> level;
17         queue<TreeNode *> q;
18         q.push(root);
19         q.push(0);
20         bool odd_even = true;
21         while (!q.empty()) {
22             TreeNode *p = q.front();
23             q.pop();
24             if (p) {
25                 level.push_back(p->val);
26                 if (p->left)
27                     q.push(p->left);
28                 if (p->right)
29                     q.push(p->right);
30             } else {
31                 if (!odd_even) {
32                     reverse(level.begin(), level.end());
33                 }
34                 
35                 odd_even = !odd_even;
36                 ret.push_back(level);
37                 level.clear();
38                 if (!q.empty())
39                     q.push(0);
40                   
41             }
42         }
43         
44         return ret;
45     }
46 };

思路二：用两个栈。一个记录当前层节点，一个记录下一层节点。

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
13         vector<vector<int> > ret;
14         if (root == nullptr) return ret;
15         
16         vector<int> level;
17         stack<TreeNode *> current,next;
18         bool odd_even = true;
19         
20         current.push(root);
21         while (!current.empty()) {
22             while (!next.empty()) {
23                  TreeNode *p = current.top();
24                 current.pop();
25                 level.push_back(p->val);
26             
27                 if (odd_even) {
28                     if (p->left)
29                         next.push(p->left);
30                     if (p->right)
31                         next.push(p->right);
32                 } else {
33                     if (p->right)
34                         next.push(p->right);
35                     if (p->left)
36                         next.push(p->left);
37                 }
38             }
39 
40             ret.push_back(level);
41             level.clear();
42             swap(current, next);
43             odd_even = !odd_even;
44 
45         }
46         
47         return ret;
48     }
49 };