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

/*
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:
//和BM26大同小异。只是添加了一个判断条件，第一行不反转已遍历的队列，偶数列反转已遍历的队列即可
    void z_order(TreeNode* Node,vector<vector<int>>&ans){
        if(Node == NULL) return;
        queue<TreeNode*> q;
        q.push(Node);
        bool flag = true;
        while (!q.empty()) {
             vector<int> row;
             int n = q.size();
             flag = !flag;
             for(int i =0;i<n;i++){
                TreeNode *temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
             }
             if(flag) reverse(row.begin(),row.end());//通过flag确定是否反转已遍历的队列
             ans.push_back(row);
        }
    } 
    vector<vector<int> > Print(TreeNode* pRoot) {
         vector<vector<int> >  ans;
         z_order(pRoot, ans);
         return ans;
    }
    
};