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

#include<stack>
#include <queue>

class Solution1 {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if (pRoot == nullptr)
            return res;

        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(pRoot);
        TreeNode* cur;

        while (!s1.empty() || !s2.empty()) {
            vector<int> ret;
            while (!s1.empty()) {
                cur = s1.top();
                ret.push_back(cur->val);
                s1.pop();
                if (cur->left)
                    s2.push(cur->left);
                if (cur->right)
                    s2.push(cur->right);
            }
            if (!ret.empty())
                res.push_back(ret);
            ret.clear();
            while (!s2.empty()) {
                cur = s2.top();
                s2.pop();
                ret.push_back(cur->val);
                if (cur->right)
                    s1.push(cur->right);
                if (cur->left)
                    s1.push(cur->left);
            }
            if (!ret.empty())
                res.push_back(ret);
        }
        return res;
    }
};

class Solution {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if (pRoot == nullptr)
            return res;

        queue<TreeNode*> q;
        q.push(pRoot);
        bool flag = true;
        TreeNode* cur;

        while (!q.empty()) {
            vector<int> ret;
            int n = q.size();
            flag = !flag;

            for (int i = 0; i < n; ++i) {
                cur = q.front();
                q.pop();
                ret.push_back(cur->val);

                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
            }

            if(flag)
                reverse(ret.begin(),ret.end());
            res.push_back(ret);

        }
        return res;
    }
};