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

又是层序遍历！！！

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
    
     
      > zigzagLevelOrder(TreeNode* root) {        queue
      
        nodes;    	vector< vector
       
         > result;    	vector
        
          tmp;    	if(NULL==root)    		return result;    	nodes.push(root);    	bool flag=false;    	while(!nodes.empty())    	{    		int length=nodes.size();    		int i=0;    		while(i
         
          val); if(tmpNode->left) nodes.push(tmpNode->left); if(tmpNode->right) nodes.push(tmpNode->right); nodes.pop(); i++; } if(flag) { reverse(tmp.begin(),tmp.end()); flag=false; } else { flag=true; } result.push_back(tmp); tmp.clear(); } return result; }};