Binary Tree Zigzag Level Order Traversal


		Question ：
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]
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
 
Anwser 1 ：       
[cpp]  
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        vector<vector<int>> ret;  
        if(root == NULL) return ret;  
          
        vector<int> vec;  
        stack<TreeNode *> Q;  
        stack<TreeNode *> Q2;   // extra space  
        bool flag = true;  
          
        Q.push(root);  
        while(!Q.empty()){  
            TreeNode *tmp = Q.top();  
            Q.pop();  
              
            if(tmp != NULL){  
                vec.push_back(tmp->val);  
                if(flag){  
                    if(tmp->left) Q2.push(tmp->left);  
                    if(tmp->right) Q2.push(tmp->right);  
                } else {  
                    if(tmp->right) Q2.push(tmp->right);  
                    if(tmp->left) Q2.push(tmp->left);  
                }  
            }  
              
            if(Q.empty()){      // one row end  
                ret.push_back(vec);  
                vec.clear();  
                flag = !flag;  
                swap(Q, Q2);  
            }  
        }  
        return ret;  
    }  
};

补充：综合编程 , 其他综合 ,