# binary tree zigzag level order travelsal

## binary tree zigzag level order travelsal

### Like level travel

Using two queues or two stack could resolve this problem.When push tv to result, do not forget to check the sizeof tv.(If a tree has only one root TreeNode.)

`````` 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 > > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         stack < TreeNode* > S1;
19         stack < TreeNode* > S2;
20         while ( !S1.empty() ) {
21             S1.pop();
22         }
23         while ( !S2.empty() ) {
24             S2.pop();
25         }
26         S1.push(root);
27         vector < int > tv;
28         tv.clear();
29         while ( !S1.empty() || !S2.empty() ) {
30             while ( !S1.empty() ) {
31                 TreeNode* t = S1.top();
32                 S1.pop();
33                 tv.push_back(t->val);
34                 if ( t->left ) {
35                     S2.push(t->left);
36                 }
37                 if ( t->right ) {
38                     S2.push(t->right);
39                 }
40             }
41             if ( tv.size() > 0 ) {
42                 result.push_back(tv);
43                 tv.clear();
44             }
45             while ( !S2.empty() ) {
46                 TreeNode* t = S2.top();
47                 S2.pop();
48                 tv.push_back(t->val);
49                 if ( t->right ) {
50                     S1.push(t->right);
51                 }
52                 if ( t->left ) {
53                     S1.push(t->left);
54                 }
55             }
56             if ( tv.size() > 0 ) {
57                 result.push_back(tv);
58                 tv.clear();
59             }
60         }
61         return result;
62     }
63 };``````