后序遍歷非遞歸法

后續(xù)遍歷，非遞歸法相對(duì)于前中序稍微復(fù)雜一點(diǎn)，因?yàn)樗枰涗洰?dāng)前節(jié)點(diǎn)是否已經(jīng)遍歷過了。

三種方法：1）使用prev，記錄輸出的前一個(gè)節(jié)點(diǎn) 2）使用visible方法【直接記錄當(dāng)前節(jié)點(diǎn)是否訪問過】。

3）對(duì)于這些非遞歸法，都可以使用顏色法【準(zhǔn)備第二個(gè)棧，表示當(dāng)前節(jié)點(diǎn)是否訪問過，若訪問過，直接輸出】。

1.常規(guī)方法

左中右、左中右、左右中。

都是先對(duì)左節(jié)點(diǎn)做處理，因此可以先把左節(jié)點(diǎn)放到棧里。

然后取出一個(gè)節(jié)點(diǎn)，考慮處理右節(jié)點(diǎn)?！颈容^難理解】

需要注意

主要元素：棧、root

root 當(dāng)前待遍歷節(jié)點(diǎn)。 棧：取出下一個(gè)節(jié)點(diǎn)

如果右節(jié)點(diǎn)沒有的話，或者無需向右遍歷，那就把root置為空指針

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        //左右中
        stack<TreeNode* > mem;
        vector<int>res;
        if(!root)
            return res;
        TreeNode* pre=nullptr;
        while(root||!mem.empty()){
            while(root){//先把root左節(jié)點(diǎn)加入
                mem.push(root);
                root=root->left;
            }
            root=mem.top();
            mem.pop();
            //加右節(jié)點(diǎn)，前提
            if(root->right==pre||root->right==nullptr){//右節(jié)點(diǎn)已經(jīng)遍歷
                res.push_back(root->val);
                pre=root;
                root=nullptr;
            }else{//右節(jié)點(diǎn)先處理
                mem.push(root);
                root=root->right;

            }

            //可以用visible來表示，不用visible就得用pre指針

        }
        return res;

    }
};

2.使用visible思路，而非prev指針。

總之先遍歷每一個(gè)節(jié)點(diǎn)的左樹。然后對(duì)當(dāng)前情況分組處理。1.是當(dāng)前節(jié)點(diǎn)已被訪問過。直接輸出。否則，先看當(dāng)前節(jié)點(diǎn)和它的右節(jié)點(diǎn)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        //左右中
        stack<TreeNode* > mem;
        map<TreeNode* ,int> a;
        vector<int>res;
        if(!root)
            return res;
        TreeNode* pre=nullptr;
        while(root||!mem.empty()){
            while(root){//先把root左節(jié)點(diǎn)加入
                mem.push(root);
                a[root]=1;
                root=root->left;
            }
        
            root=mem.top();
            mem.pop();
            if(a[root]>1||!root->right){
                res.push_back(root->val);
                root=nullptr;
            }else{
                mem.push(root);
                a[root]=2;
                root=root->right;
            }
            
        }
        return res;

    }
};

3.顏色標(biāo)記法。【實(shí)際上是中右左換成左右中】

可以使用兩個(gè)棧，或者使用pair對(duì)。

左右中——》重新push時(shí)是 中左右，入棧。

開始先把節(jié)點(diǎn)push到棧中（但是只是輔助遍歷，并不輸出）

然后從棧中取出節(jié)點(diǎn)，按照中 左 右的順序重新push（中節(jié)點(diǎn)，因?yàn)槿〕鲞^一次，認(rèn)為已經(jīng)處理過，就標(biāo)記處理過，再取出時(shí)直接輸出就可）,沒有處理過的，繼續(xù)按照中左右順序遍歷。

【這里新加一個(gè)棧，存標(biāo)記，也可以用pair對(duì)】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        //左右中

        stack<TreeNode*> res;
        stack<int> biaoji;
        vector<int> rr;
        if(!root)
            return rr;
        res.push(root);
        biaoji.push(1);
        
        TreeNode* tmp;
        int tmpb;
        while(!res.empty()){
            tmp=res.top();
            tmpb=biaoji.top();
            res.pop();
            biaoji.pop();
            //cout<<tmp->val<<"\t"<<tmpb<<endl;
            if(tmpb==1){
                res.push(tmp);
                biaoji.push(2);
                if(tmp->right){
                    res.push(tmp->right);
                    biaoji.push(1);
                }            
                if(tmp->left){
                    res.push(tmp->left);
                    biaoji.push(1);
                }                
                    
            }else{
                rr.push_back(tmp->val);

            }
        }
        return rr;

    }
};

前序遍歷【中左右】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root){
            return res;
        }//中左右
        stack<TreeNode*> tmp;
        while(root||!tmp.empty()){
            while(root){
                tmp.push(root);
                res.push_back(root->val);
                root=root->left;
            }
            root = tmp.top();
            tmp.pop();
            //看右
            if(root->right){
                root=root->right;
            }else{
                root=nullptr;
            }
            
        }
        return res;



    }
};

中序遍歷【左中右】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root){
            return res;
        }//左中右
        stack<TreeNode*> tmp;
        while(root||!tmp.empty()){
            while(root){
                tmp.push(root);
                
                root=root->left;
            }
            root = tmp.top();
            tmp.pop();
            res.push_back(root->val);
            //看右
            if(root->right){
                root=root->right;
            }else{
                root=nullptr;
            }
            
        }
        return res;
    }
};