栈模拟先序后序中序遍历（非递归遍历）

本文介绍: 所以我们可以把先序遍历的左右子树的遍历顺序倒一下便变成了后序遍历的倒序。后序遍历与先序遍历有互通之处，即后序遍历的倒序为：根右左。中序遍历没有找到优化版，，

先序 遍历：

vector&lt;int&gt; preorderTraversal(TreeNode* u) {
        stack<TreeNode*>stk;
        vector<int>res;
        if(u==nullptr) return res;
        while(stk.size()||u){
            if(u){
                res.push_back(u->val);//遍历当前结点
                stk.push(u);//记录当前递归层
                u=u->left;//遍历左子树
            }else {
                u=stk.top();stk.pop();//返回上一层递归层
                u=u->right;//遍历右子树
            }
        }
        return res;
    }

优化版：

vector<int> preorderTraversal(TreeNode* u) {
        stack<TreeNode*>stk;
        vector<int>res;
        if(u==nullptr) return res;

        stk.push(u);
        while(stk.size()){
            auto t=stk.top();stk.pop();
            res.push_back(t->val);
            if(t->right)stk.push(t->right);//后遍历的先入栈，即右子树先入栈
            if(t->left)stk.push(t->left);//先遍历的后入栈，即左子树后入栈
        }
        return res;
    }

后序遍历：

后序遍历与先序遍历有互通之处，即后序遍历的倒序为：根右左。

所以我们可以把先序遍历的左右子树的遍历顺序倒一下便变成了后序遍历的倒序。

vector<int> postorderTraversal(TreeNode* u) {
        stack<TreeNode*>stk;
        vector<int>res;
        if(u==nullptr) return res;
        
        while(stk.size()||u){
            if(u){
                res.push_back(u->val);//遍历当前结点
                stk.push(u);//记录下该层的遍历
                u=u->right;//先遍历右子树
            }else {
                u=stk.top();stk.pop();
                u=u->left;//再遍历左子树
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }

同样有优化版：

vector<int> postorderTraversal(TreeNode* u) {
        stack<TreeNode*>stk;
        vector<int>res;
        if(u==nullptr) return res;
        stk.push(u);
        while(stk.size()){
            TreeNode* t=stk.top();stk.pop();
            res.push_back(t->val);
            if(t->left)stk.push(t->left);
            if(t->right)stk.push(t->right);
        }
        reverse(res.begin(),res.end());
        return res;
    }

中序遍历：

vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>stk;
        while(stk.size()||root)
        {
            if(root)
            {
               	stk.push(root);//相当于记录下了当前层递归
           		root=root->left;//先遍历左子树
            }
            else
            {
                root=stk.top();//返回上一层递归
                stk.pop();
                res.push_back(root);//遍历当前结点
                root=root->right;//遍历右子树
            }
        }
        return res;
    }