[数据结构与算法]从上到下打印二叉树

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

本题还是在二叉树层次遍历的基础上改动过来的，有需要的话，可以先看看我前两篇的题解，有助于理解此题：

https://blog.csdn.net/qq_54669536/article/details/123940163

https://blog.csdn.net/qq_54669536/article/details/123941309

思路解析：此题其实就是二叉树的Z字形遍历，对于此题，我们常用的有两种方法：

方法一：使用双栈解决，我们可以定义两个栈st1和st2,将根节点首先入栈st1,然后再判断st1不为空的情况下，出栈，再将出栈元素的左孩子和右孩子入栈到st2；对于st2，我们同样先判断是否为空，若不为空，将st2中的元素依次出栈同时将其左孩子和右孩子入栈到st1;重复上述步骤，即可达到Z字形遍历。需要注意的是，我们先从左到右，再从右到左进行循环，因此在入栈st1时，就是先right再left,在入栈到st2时，先入栈left再right)

代码实现：

vector<vector<int>> levelOrder(TreeNode* root) {
	stack<TreeNode*>st1;
	stack<TreeNode*>st2;
    vector<vector<int>>res;
	if(root!=NULL)st1.push(root);
    TreeNode* ptr=root;
	while (!st1.empty()||!st2.empty())
	{
        if(!st1.empty())
        {
             vector<int>qu1;
		     while(!st1.empty())
		     { 
		     	ptr = st1.top(); 
                st1.pop();
			    qu1.push_back(ptr->val);
			    if (ptr->left != NULL)st2.push(ptr->left);
			    if (ptr->right != NULL)st2.push(ptr->right);
		     }
             res.push_back(qu1);
        }
        if(!st2.empty())
        {
             vector<int>qu2;
		     while (!st2.empty())
		     {
		    	ptr = st2.top(); 
                st2.pop();
		    	qu2.push_back(ptr->val);
                if (ptr->right != NULL)st1.push(ptr->right);
			   if (ptr->left != NULL)st1.push(ptr->left);
		     }
             res.push_back(qu2);
        }
	}
    return res;
    }

说明：代码中所有对容器的操作都是为了返回值是一个二维数组形式，和题目本身没有关系。

方法二：除了使用双栈外，我们还可以通过队列来解决，通过奇偶数来判断所处的层次。根节点就是第0层，是偶数层。在具体实现时，如果是偶数层的数据，我们就将数据从左到右依次放在返回容器中，如果是奇数层的数据，我们就将数据从右到左放入返回容器中(需要注意的是，我们在将下一层的节点入队之前，需要先获得上一层节点的个数)

代码实现：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL) return result;
        queue<TreeNode*> que;
        que.push(root);
        int level = 0;
        while(!que.empty()) 
        {
            int len = que.size();//这里先存储了每一层数组的大小
            result.push_back(vector<int>(len));//首先根据每层数组大小进行拓展

            for(int i = 0; i < len; ++i) 
            {
                TreeNode* cur = que.front();
                que.pop();
                if(level % 2 == 0) 
                {//根据奇偶层进行从前到后或者从后向前的赋值
                    result[level][i] = cur->val;
                } 
                else 
                 {
                    result[level][len-i-1] = cur->val;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            ++level;
        }
        return result;
    }
};