二叉树的前中后序遍历 C++ 非递归

三种遍历的思路都是从跟开始遍历，将树分为根和左数，用栈存起来，根据栈的特性，改变访问根的时机

前序：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;  
        stack<TreeNode*>st;

        TreeNode*cur=root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }

            TreeNode*top=st.top();
            cur=top->right;
            st.pop();
        }

        return ret;

    }
};

中序：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*>st;

        TreeNode*cur=root;
        while(cur||!st.empty())
        {

            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            
            TreeNode*top=st.top();
            ret.push_back(top->val);
            cur=top->right;
            st.pop();
        }
        return ret;
    }
};

后序：

（后序要麻烦一些，因为根是最后一个被记录，所以需要记录右数是否被记录）

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> ret;  
        stack<TreeNode*>st;
        TreeNode*LastNode=nullptr;
        TreeNode*cur=root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
                
            }
            
            TreeNode*top=st.top();
            if(top->right==nullptr||LastNode==top->right)
            {
                ret.push_back(top->val);
                LastNode=top;
                st.pop();
            }
            else
            {
                cur=top->right;   
            }
        
            
        }

        return ret;
    
    }
};