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

//主要思路是设计一个标记nowToleft:
//记录当前是从左往右打印（nowToLeft=true）还是从右往左打印(nowToleft=false).
//然后准备一个栈，如果当前从左往右，则先压左再压右；否则，先压右再压左。往复这个过程就可以完成了。
#include <vector>
class Solution {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        // write code here
        stack<TreeNode*> layerStack;
        stack<TreeNode*> restoreStack;
        stack<TreeNode*> empty;
        vector<vector<int>> result;
        vector<int> tempVec;

        if(pRoot == nullptr){
            return result;
        }

        bool nowToLeft = true;
        layerStack.push(pRoot);
        restoreStack.push(pRoot);
        while (!restoreStack.empty()) {
            restoreStack = empty;
            while (!layerStack.empty()) {
                pRoot = layerStack.top();
                tempVec.push_back(pRoot->val);
                layerStack.pop();

                if (nowToLeft) {
                    if(pRoot->left != nullptr)
                        restoreStack.push(pRoot->left);
                    if(pRoot->right != nullptr)
                        restoreStack.push(pRoot->right);
                } else {
                    if(pRoot->right != nullptr)
                        restoreStack.push(pRoot->right);
                    if(pRoot->left != nullptr)
                        restoreStack.push(pRoot->left);
                }
            }
            nowToLeft = !nowToLeft;
            layerStack = restoreStack;
            result.push_back(tempVec);
            tempVec.clear();
        }
        return result;
    }
};