Binary Tree Zigzag Level Order Traversal (C++ code)

LeetCode Binary Tree Zigzag Level Order Traversal, Sep 29 '12
难度4，出现频率3
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},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]

]

思路： 跟level order traversal一致，只是多一个flag记录每层正向还是逆向。

0. vector<vector<int>> zigzagLevelOrder(TreeNode *root){  
1.   vector<vector<int>> res;  
2.   if(!root) return res;   
3.   vector<int> level;  
4.   queue<TreeNode *> myque;  
5.   bool flag = true;   
6.   TreeNode *last = root;  
7.   myque.push(root);   
8.   //main loop  
9.   while(!myque.empty()){  
10.    root = myque.front();  
11.    myque.pop();  
12.    if(root->left) myque.push(root->left);  
13.    if(root->right) myque.push(root->right);  
14.    if(flag == true)level.push_back(root->val);  
15.    else level.insert(level.begin(), root->val);  
16.    //when current level ends, store level in result, reset flag and level variable.  
17.    if(root == last){  
18.      res.push_back(level);  
19.      level.clear();  
20.      last = myque.back();  
21.      flag = !flag;   
22.    }   
23.   }  
24.   return res;   
25. }