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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <queue>
#include <vector>
class Solution {
public:
// 用来反转vector操作
    vector<int> reverse(vector<int> it)
    {
        vector<int> jt;
        // 遍历vector的全部数据有顺序和逆序
        // 如果顺序的话是begin到end
        // 如果是逆序的话是end-1到begin-1
        // 这是因为end指向的是vector后一个数据，要从end-1开始。同样的，逆序的begin应该也指向顺序begin前一个数据，也就是begin-1
        // begin=0，end=n
        for (auto k=it.end()-1; k!=it.begin()-1; k--) {
            jt.push_back(*k);
        }
        return jt;
    }

// 这就是层序遍历，参考上一篇文章
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > vec;
        if(pRoot==nullptr)return vec;
        queue<TreeNode*> qu;
        TreeNode *node=pRoot;
        qu.push(node);
        // 本来还想着通过存储在队列的方式来改变输出vector，但我发题目的规律后发现奇数层是反转的，那直接层序遍历修改一下不就好咯！所以就没必要再在这里耗下去了，转化思路！
        // int count=1;
        while (qu.empty()==false) {
            vector<int> temp;
            int _size = qu.size();
            for (int i=0; i<_size; ++i) {
                node=qu.front();
                qu.pop();
                temp.push_back(node->val);
                if (node->left!=nullptr) {
                    qu.push(node->left);
                }
                if(node->right!=nullptr)
                {
                    qu.push(node->right);
                }
            }
            // count++;
            vec.push_back(temp);
            temp.clear();
        }
        // return vec;
        vector<vector<int> > final;
        for (int j=0; j<vec.size(); j++) {
            if (j%2==1) {
                vector<int> mid=reverse(vec[j]);
                final.push_back(mid);
            }else{
                final.push_back(vec[j]);
            }
        }
        vec.clear();
        return final;
    }
    
};