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

Loading Disqus comments...
Table of Contents