[Leetcode 95] 103 Binary Tree Zigzag Level Order Traversal

Problem:

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

Analysis:

A little change to the original level-order reaversal code. Add a zz flag to indicate whether or not reverse the current level's elements.

Remember that after exit the while loop, an extra push_back operation is needed !

Code:

 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         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         vector<vector<int> > res;
16         
17         if (root == NULL)
18             return res;
19         
20         vector<int> l;
21         
22         queue<TreeNode*> q;
23         q.push(root);
24         
25         TreeNode *senti = new TreeNode(-1);
26         senti->left = senti->right = NULL;
27         q.push(senti);
28         
29         bool zz = false;
30         
31         while (q.size() != 1) {
32             TreeNode *n = q.front();
33             q.pop();
34             
35             if (n == senti) { // get the sentinal node
36                 if (zz) reverse(l.begin(), l.end());
37                 
38                 res.push_back(l);
39                 q.push(n);
40                 zz = !zz;
41                 l.clear();
42             } else {
43                 l.push_back(n->val);
44             
45                 if (n->left != NULL) q.push(n->left);
46                 if (n->right != NULL) q.push(n->right);
47             }
48         }
49         if (zz) reverse(l.begin(), l.end());
50         res.push_back(l);
51         
52         return res;
53     }
54 };

View Code