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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <vector>
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        stack<TreeNode*> input;

        vector<vector<int>> ret;
        if(pRoot==nullptr)
            return ret;
        
        input.push(pRoot);
        int depth=1;
        while(!input.empty()){
            vector<int> psh;
            queue<TreeNode *> ptrpsh;

            //process middle
            while(!input.empty()){
                TreeNode * cur=input.top();
                psh.push_back(cur->val);
                ptrpsh.push(cur);
                input.pop();
            }

            //process next and push
            ret.push_back(psh);

            while(!ptrpsh.empty()){
                TreeNode * cur=ptrpsh.front();
                if(depth%2==1){
                    //left to right
                    
                    if(cur->left!=nullptr){
                        input.push(cur->left);
                    }
                    if(cur->right!=nullptr){
                        input.push(cur->right);
                    }
                }
                else{
                    if(cur->right!=nullptr){
                        input.push(cur->right);
                    }
                    if(cur->left!=nullptr){
                        input.push(cur->left);
                    }
                }
                ptrpsh.pop();
            }
            depth++;

        }
        //init ret and stack
        //when the stack
        //push to a ret .scan the ret,add the subnodes into the stack in specific ways.
        //continue,untill there is nothing can be add to the stack,quit

        return ret;
    }
    
};

//首先想到了栈

//主要卡在，出栈时，怎么同时存储子树

//其次，不同层次，先入左还是先入右有区别，使用标记来记录层次

//第三，储存的是指针，用于访问左右子树

//第四，每次循环处理一段，大循环处理多段