解法一：使用队列

据题意，需要按照每一层的方式打印二叉树，因此较为直接的解法为「层次遍历」。

二叉树的层次遍历通过队列实现较为方便，步骤如下：

初始情况，根结点入队列；
定义变量size记录当前队列长度；
对于「当前队列」，遍历其所有元素：依次出队列、访问该元素、左右孩子入队列。注意：新入队列的「左右孩子」应当在下一层被访问，因此循环次数为size次。
重复上述步骤直至队列为空。

步骤如图所示。

图片说明

此外，此题目要求「之字形」打印，因此定义变量level记录当前层的打印方向。

代码如下：

/*
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; 
        if (!pRoot)
            return res; 
        queue<TreeNode*> q; // 定义队列
        q.push(pRoot); // 根结点入队列
        int level = 0;
        while (!q.empty()) {
            vector<int> arr; // 定义数组存储每一行结果
            int size = q.size(); // 当前队列长度
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = q.front(); // 队头元素
                q.pop(); 
                if (!tmp) // 空元素跳过
                    continue;
                q.push(tmp->left); // 左孩子入队列
                q.push(tmp->right); // 右孩子入队列
                if (level % 2 == 0) {
                    // 从左至右打印
                    arr.push_back(tmp->val);
                } else { // 从右至左打印
                    arr.insert(arr.begin(), tmp->val);
                }
            }
            level++; // 下一层，改变打印方向
            if (!arr.empty())
                res.push_back(arr); // 放入最终结果
        }
        return res;
    }

};

该方法遍历到树的所有结点，时间复杂度为O(N)；该方法定义了队列q，空间复杂度为O(N)。

解法二：使用栈

由本题所要求的「之字形打印」，可以联想到栈的「先入后出」的特性。由于栈仅能在一端进行入栈出栈操作，因此需要定义两个栈，交替使用。

步骤如下（如图所示）：

定义两个栈stk1，stk2；将根结点入栈stk1；
对于下一层，应是「从右至左」打印，因此需要遍历栈stk1、访问每一个元素，并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk2；将访问的结点保存；
对于下一层，应是「从左至右」打印，因此需要遍历栈stk2、访问每一个元素，并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk1；将访问的结点保存；
重复上述操作，直至两个栈全为空。

图片说明

根据上述思路，实现的代码如下：

/*
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; 
        if (!pRoot) 
            return res; 
        stack<TreeNode*> stk1, stk2; // 定义两个栈
        stk1.push(pRoot); // 根结点入栈
        while (!stk1.empty() || !stk2.empty()) { // 两个栈全空时循环结束
            vector <int> arr; 
            while (!stk1.empty()) {
                TreeNode* p = stk1.top(); 
                stk1.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->left) stk2.push(p->left); // 左孩子入栈
                if (p->right) stk2.push(p->right); // 右孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
            arr.clear(); // 清空
            while (!stk2.empty()) {
                TreeNode* p = stk2.top(); 
                stk2.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->right) stk1.push(p->right); // 右孩子入栈
                if (p->left) stk1.push(p->left); // 左孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
        }
        return res;
    }

};

该方法遍历到树的所有结点，时间复杂度为O(N)；该方法定义了双栈，空间复杂度为O(N)。

题解 | #按之字形顺序打印二叉树#

解法一：使用队列

解法二：使用栈