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

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

This problem cost me a lot of time, even though it seems like an easy binary tree traversal problem. my poor skills for handling complex abstract was laid bare(again) finding yourself is not so clever is always frustrated.
Anyway, I do came up this idea almost alone :) I believe if I keep pushing forward I can be better and better. and actually Im pretty enjoy this kinda shit.

This problem is very similar to level order traversal, but its zigzag manner makes it a little tricky. By using two stacks, one for left->right, one for right->left, and switch between as long as the current-selected stack is empty.
using a boolean value to determines the direction, and the direction determines which stack we have to pushed in.

pop from the current-selected stack as currentNode, push the value in the level array.(if current-selected stack is empty, terminate the function.)
if current turn is a "left" turn, then we push left then right child of currentNode in another stack.
if current turn is a "right" turn, then we push right then left child of currentNode in another stack.
then if current-selected stack is empty, reverse the current-direction, make current-selected statck to another stack, merge the level with final result, realloc a new level array, then starts over.

My AC version:

 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         if (!root) return vector<vector<int>>();
14         stack<TreeNode*> left;
15         stack<TreeNode*> right;
16         vector<stack<TreeNode*>> stacks;
17         vector<vector<int>> result;
18         int direction = 0;
19         stacks.push_back(left);
20         stacks.push_back(right);
21         stacks[direction].push(root);
22         
23         stack<TreeNode*>* cs;
24         vector<int> level;
25         while ((cs = &stacks[direction]) && !cs->empty()){
26             TreeNode* currentNode = cs->top();
27             if (currentNode){
28                 level.push_back(currentNode->val);
29             }
30             cs->pop();
31             stack<TreeNode*>* nextStack = &stacks[(direction+1)%2];
32             if (!direction){
33                 //left
34                 if (currentNode->left)
35                     nextStack->push(currentNode->left);
36                 if (currentNode->right)
37                     nextStack->push(currentNode->right);
38             }
39             else{
40                 //right
41                 if (currentNode->right)
42                     nextStack->push(currentNode->right);
43                 if (currentNode->left)
44                     nextStack->push(currentNode->left);
45             }
46             if (cs->empty()){
47                 direction = (direction + 1)%2;
48                 result.push_back(level);
49                 level = vector<int>();
50             }
51         }
52         return result;
53     }
54 };