二叉树前中后序的非递归排序

前序

        

class Solution {
public:
    vector preorderTraversal(TreeNode* root) 
    {
        vector v;
        stack st;
        TreeNode* cur = root;
        while(!st.empty() || cur)
        {
            // 每次循环表示要开始访问一颗树了，先将一颗数的左路节点都入栈并访问节点
            // 剩余左路节点的右子树还没访问
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
 
 
            // 取栈中的节点依次访问左路节点的右子树
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }
 
 
        return v;
    }
};
 

中序

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        
        // 空树，直接返回
        vector vRet;
        if(nullptr == root)
            return vRet;
        
        TreeNode* pCur = root;
        stack s;
        while(pCur || !s.empty())
        {
            // 找以pCur为根的二叉树最左侧的节点，并将所经路径中的节点入栈
            while(pCur)
            {
                s.push(pCur);
                pCur = pCur->left;
            }
 
            pCur = s.top();
            
            // pCur左子树为空，相当于左子树已经访问过了，可以直接访问以pCur为根的二叉树的根节点
            vRet.push_back(pCur->val);
            s.pop();
            
            // 以pCur为根的二叉树的左子树已经遍历完，根节点已经遍历，
            // 将pCur的右子树当成一棵二叉树来遍历
            pCur = pCur->right;
        }
 
        return vRet;
    }
};
 

后序

 vector postorderTraversal(TreeNode* root) {
        vector v;
        if(root==nullptr)
            return v;
        TreeNode* pcur=root;
        TreeNode* pPrev=nullptr;
        stack st;
        while(pcur||!s.empty())
        {
            while(pcur)
            {
                s.push(pcur);
                pcur=pcur->left;
            }
            TreeNode* ptop=s.top();


            if(ptop->right==nullptr||pPrev==ptop->right)
            {
                v.push_back(ptop->val);
                s.pop();
                pPrev=ptop;
            }
            else
            {
                pcur=ptop->right;
            }
            
        }
        return v;
    }