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]
]

思路

宽搜的变形，在宽搜的基础上加一个栈，用于在偶数行反向输出。

 1      vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         vector<vector<int> > result;
 4         if(root == NULL)
 5             return result;
 6         vector<int> tmp;
 7         int type = 1;
 8         TreeNode * tPoint;
 9         stack<int> aStack;
10         queue<TreeNode*> aQueue1, aQueue2;
11         aQueue1.push(root);
12         while(!aQueue1.empty() || !aQueue2.empty()){
13             tmp.clear();
14             if(type){
15                 while(!aQueue1.empty()){
16                     tPoint = aQueue1.front();
17                     aQueue1.pop();
18                     tmp.push_back(tPoint->val);
19                     if(tPoint->left != NULL)
20                         aQueue2.push(tPoint->left);
21                     if(tPoint->right != NULL)
22                         aQueue2.push(tPoint->right);
23                 }
24                 result.push_back(tmp);
25                 type = (type+1)%2;
26             }
27             else{
28                 while(!aQueue2.empty()){
29                     tPoint = aQueue2.front();
30                     aQueue2.pop();
31                     aStack.push(tPoint->val);
32                     if(tPoint->left != NULL)
33                         aQueue1.push(tPoint->left);
34                     if(tPoint->right != NULL)
35                         aQueue1.push(tPoint->right);
36                 }
37                 while(!aStack.empty()){
38                     tmp.push_back(aStack.top());
39                     aStack.pop();
40                 }
41                 result.push_back(tmp);
42                 type = (type+1)%2;
43             }
44         }
45         return result;
46     }

第二遍，交替使用两个栈

 1      vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         vector<vector<int> > result;
 4         vector<int> tmp;
 5         if(!root)
 6             return result;
 7         stack<TreeNode *> stacks[2];
 8         bool flag = false;
 9         stacks[0].push(root);
10         while(!stacks[flag].empty() || !stacks[!flag].empty()){
11             while(!stacks[flag].empty()){
12                 TreeNode *node = stacks[flag].top();
13                 stacks[flag].pop();
14                 tmp.push_back(node->val);
15                 if(!flag){
16                     if(node->left)
17                         stacks[!flag].push(node->left);
18                     if(node->right)
19                         stacks[!flag].push(node->right);
20                 }
21                 else{
22                     if(node->right)
23                         stacks[!flag].push(node->right);
24                     if(node->left)
25                         stacks[!flag].push(node->left);
26                 }
27             }
28             result.push_back(tmp);
29             tmp.clear();
30             flag = !flag;
31         }
32         return result;
33     }