描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。

//方法1：BFS+队列 

vector<vector<int> > Print(TreeNode* pRoot) 
{
    vector<vector<int>> res;//输出数组 
    if(pRoot==NULL)
    {
    	return res;
	}
	
    queue<TreeNode*> q;//队列
	int level=0;//层数
	 
	q.push(pRoot);
	
	while(!q.empty())
	{
		int q_size=q.size();///重点：队列里存的就是该层需要遍历的数 ，通过size来确定该层次的个数 
		vector<int> ans;//用来存一层的数 
		for(int i=0;i<q_size;i++)
		{
			TreeNode* temp=q.front();
			q.pop();
			ans.push_back(temp->val); 

			if(temp->left)
			{
				q.push(temp->left);
			}
			if(temp->right)
			{
				q.push(temp->right);
			}
		
		}
		//reverse函数将偶数行反转
		if(level%2) 
		{
			reverse(ans.begin(),ans.end());
		}
		level++;
		res.push_back(ans);
		
	}
	return res;
	
	
}