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

一.题意整理

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。也就是在层次遍历的基础上实现对整个树进行之字形顺序打印。

二.思路整理

先我们根据题目的描述，能够找到该题的解决模型为二叉树的层次遍历。只不过普通的层次遍历是针对每一层都只是从左到右遍历。这里题目要求奇数层是从左到右遍历，而偶数层则是从右到左遍历的。对于层序遍历我们知道可以利用队列来实现，给出层序遍历的模板：

void LevelOrder(BTree *t){
//利用队列来实现
    Queue Q;
    initQueue(Q);
    EnQueue(Q,t);
    while(!Empty(Q)){
        TNode*p=DeQueue(Q);
        //左右节点入队列
        if(p->lchird) EnQueue(Q,p->lchird);
        if(p->rchird) EnQueue(Q,p->rchird);
    }
}

知道了层序遍历的遍历方法，下面我们就要考虑如何在遍历时候实现之字形顺序打印，由于之字形打印对于奇数和偶数层次上存在着正序和反序的区别，所以我们可以利用vector的尾插和头插来实现来实现。(第一层是从左往右，下一层就是从右往左)。

三.代码实现

class Solution {
public:
    
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>>tr;
        queue<TreeNode*>q;
        q.push(pRoot);
        int ans=0;//记录层数
        while(q.size()){
            vector<int>now;//每一层存储遍历结果
            int len=q.size();
            for(int i=0;i<len;i++){
                TreeNode* top=q.front();
                q.pop();
                if(!top) continue;
                //层次遍历
                q.push(top->left);
                q.push(top->right);
                if(ans%2){
                    //直接在开始处插入类似头插 可以实现倒序
                    now.insert(now.begin(),top->val);
                } else {
                    //直接尾插 实现了正序插入
                    now.push_back(top->val);
                }
            }
            ans++;//层数记录
            if(now.size()){
                //每一层的遍历结果插入
                tr.push_back(now);
            }
        }
        return tr;
    }
    
};