按之字形顺序打印二叉树

思路（双栈法）：

我们可以利用两个栈遍历这棵二叉树，第一个栈s1从根节点开始记录第一层，然后依次遍历两个栈，遍历第一个栈时遇到的子节点依次加入第二个栈s2中，即是第二层：而遍历第二个栈s2的时候因为是先进后出，因此就是逆序的，再将第二个栈s2的子节点依次加入第一个栈s1中：于是原本的逆序在第一个栈s1中又变回了正序，如果反复交替直到两个栈都空为止。

具体做法：

step 1：首先判断二叉树是否为空，空树没有打印结果。

step 2：建立两个辅助栈，每次依次访问第一个栈s1与第二个栈s2，根节点先进入s1.

step 3：依据依次访问的次序，s1必定记录的是奇数层，访问节点后，将它的子节点（如果有）依据先左后右的顺序加入s2，这样s2在访问的时候根据栈的先进后出原理就是右节点先访问，正好是偶数层需要的从右到左访问次序。偶数层则正好相反，要将子节点（如果有）依据先右后左的顺序加入s1，这样在s1访问的时候根据栈的先进后出原理就是左节点先访问，正好是奇数层需要的从左到右访问次序。

step 4：每次访问完一层，即一个栈为空，则将一维数组加入二维数组中，并清空以便下一层用来记录。

图示：

链接

代码：

class Solution{
    public:
    //定义一个函数用于之字形打印二叉树
    //传入二叉树的根节点，返回的是二维数组
    vector<vector<int>> Print(TreeNode* pRoot){
        //定义一个二维数组用于存最后的结果
        vector<vector<int>>res;
        TreeNode* head=pRoot;
        //如果二叉树为空，则直接返回res
        if(pRoot==NULL){
            return res;
        }
        //否则就创建两个栈，由于栈是先进后出的结构
        //所以可以先将根节点放入栈1中，再将栈1中的节点进行扩展，将扩展的点（从左节点到右节点的顺序）放入栈2中
        //再将栈2中的点进行扩展，从右子节点到左子节点进行扩展，将扩展的点放入栈1中，这样刚好能实现之字形打印二叉树
        stack<TreeNode*>s1;
        stack<TreeNode*>s2;
        s1.push(head);
        //只要栈1或栈2中有一个栈还有点没有扩展，就继续扩展
        while(!s1.empty()||!s2.empty()){
            //用一个一维数组存每层的节点的编号
            vector<int>now;
            //只要栈1的点还没有扩展完，就将每个点进行扩展，将扩展好的点输出存入now数组中，再将该点的所有子节点（从左子节点到右子节点）扩展添加到栈2中
            while(!s1.empty()){
                TreeNode* t=s1.top();
                now.push_back(t->val);
                if(t->left){
                    s2.push(t->left);
                }
                if(t->right){
                    s2.push(t->right);
                }
                s1.pop();
            }
            //将该层的节点插入最后的二维数组
            if(now.size()){
                res.push_back(now);
            }
            //将数组now清空，就可以继续存下一层的节点
            now.clear();
            //还要栈2不为空，就将栈2的点进行扩展（从右子节点到左子节点），将出栈的点插入数组中
            while(!s2.empty()){
                TreeNode* p=s2.top();
                now.push_back(p->val);
                if(p->right){
                    s1.push(p->right);
                }
                if(p->left){
                    s1.push(p->left);
                }
                s2.pop();
            }
            if(now.size()){
                res.push_back(now);
            }
        }
        return res;
    }

};