题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
       //用栈来存储结点，然后判断当前打印的层数,下一层的个数(用两个栈来分别存储奇数层和偶数层的结点，利用先进后出，后进先出的特性)
        vector<vector<int>> res;
        vector<int> out;
        stack<TreeNode*> levels[2];
        levels[0].push(pRoot);
        int current,next;
        current = 0;                          //当前哪个层
        next = 1;							  //下一层
        if(pRoot == NULL)
        {
        	return res;
        }
       
        while(!levels[0].empty() || !levels[1].empty())
        {
        	   TreeNode *node = levels[current].top();
               levels[current].pop();
               out.push_back(node->val);
            if(current == 0)
            {
            	if(node->left != NULL)
                {
                	levels[next].push(node->left);    
                }
                if(node->right != NULL)
            	{
                    levels[next].push(node->right);
                }
            }
            else 
            {
            	if(node->right != NULL)
                {
                	levels[next].push(node->right);    
                }
                if(node->left != NULL)
                {
                	levels[next].push(node->left);    
                }
            }
            if(levels[current].empty())
            {
            	res.push_back(out);
                out.clear();
                current = 1 - current;
                next = 1- next;
            }
            
        }
        return res;
        
        
    }
	
	
	
	//另外一种方法
	  queue<TreeNode *> q;
        vector<vector<int>> res;
        if(pRoot == NULL)
        {
        	return res;    
        }
        q.push(pRoot);
        int cnt = 1;
        int level = 1;
        while(!q.empty())
        {
            int number = cnt;
            cnt = 0;
            vector<int> out;
            while(number > 0)
            {
            	TreeNode *cur = q.front(); 
                out.push_back(cur->val);
                q.pop();
                number--;
                if(cur->left != NULL)
                {
                	q.push(cur->left);    
                	cnt++;
                }
                if(cur->right != NULL)
                {
                	q.push(cur->right);    
                	cnt++;
                }
            }
            if(level % 2 == 0)
            {
            	reverse(out.begin(),out.end());
            }
            level++;
            res.push_back(out);
        }
        
        return res;
    
};