按之字顺序打印二叉树

---

题目描述

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

解题思路

这个题是二叉树层序遍历的一个变型，一般二叉树层序遍历可以通过一个队列（queue）来存放每层的结点，但是本题要求先从左到右，然后从右到左，依次输出每层结点。这就不能使用先进先出的队列（queue）容器了，而要考虑先进后出的栈（stack）容器。

只需构造两个栈，分别存放偶数层结点和奇数层结点，然后输出即可。

问题是两个栈的结点的存入顺序？

为了实现之字型输出：A C B D E F G.需要对存奇数层的栈，实行先压入要删除结点的右结点再压入左结点；对存入偶层的栈，先压入删除结点的左结点再压入右结点。

其中红线表示指向右结点，绿线表示左结点。

代码

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> > result;
        if (pRoot == NULL)
            return result;
        
        stack<TreeNode*> s[2]; // 创建两个栈，分别存放奇数层和偶数层结点
        s[1].push(pRoot); // s[1] 存放奇数层结点
        while (!s[0].empty() || !s[1].empty())
        {
            // 存放偶数层结点，先存左结点，再存右结点
            vector<int> temp1; // 存放每层的结点数值
            while (!s[1].empty())
            {
                TreeNode* top = s[1].top();
                if (top->left != NULL)
                    s[0].push(top->left);
                if (top->right != NULL)
                    s[0].push(top->right);
                temp1.push_back(top->val);// 将栈顶元素的值压入临时容器中
                s[1].pop(); // 删除栈顶元素
            }
            if (!temp1.empty())
                result.push_back(temp1);
            
            // 存放奇数层结点
            vector<int> temp2; // 存放偶数层结点
            while (!s[0].empty())
            {
                TreeNode* top = s[0].top();
                if (top->right != NULL)
                    s[1].push(top->right);
                if (top->left != NULL)
                    s[1].push(top->left);
                temp2.push_back(top->val);
                s[0].pop();
            }
            if (!temp2.empty())
                result.push_back(temp2);
        }
        return result;
    }
    
};

---

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_59.html