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

1. 双栈法：用两个栈分别存奇数层和偶数层，入栈的顺序需要注意：奇数层从右往左，偶数层从左往右

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        int n = 1;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        vector<vector<int>> res;
        if(!pRoot)
            return res;
        else
            s1.push(pRoot);
        while(!s1.empty() || !s2.empty()){
            vector<int> temp;
            if(n % 2){
                while(!s1.empty()){
                    temp.push_back(s1.top()->val);
                    if(s1.top()->left)
                        s2.push(s1.top()->left);
                    if(s1.top()->right)
                        s2.push(s1.top()->right);
                    s1.pop();
                }
            }
            else{
                while(!s2.empty()){
                    temp.push_back(s2.top()->val);
                    if(s2.top()->right)
                        s1.push(s2.top()->right);
                    if(s2.top()->left)
                        s1.push(s2.top()->left);
                    s2.pop();
                }
            }
            n ++;
            if(temp.size())
                res.push_back(temp);
        }
        return res;
    }
    
};

2. 一个队列：层次遍历，偶数层时将返回数组逆转

class Solution {
public:
    vector<vector<int>> Print(TreeNode* pRoot) {
        vector<vector<int>> ret;
        if (!pRoot) return ret;
        queue<treenode*> q;
        q.push(pRoot);
        int level = 0;
        while (!q.empty()) {
            int sz = q.size();
            vector<int> ans;
            while (sz--) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++level;
            if (!(level%1)) // 偶数层 反转一下
                reverse(ans.begin(), ans.end());
            ret.push_back(ans);
        }
        return ret;
    }
    
};