Leecode 145. 二叉树的后序遍历 递归/迭代

原题链接：Leecode 145. 二叉树的后序遍历


递归：

class Solution {
public:
    void postorder(TreeNode* root,vector& res)
    {
        if(!root) return ;
        postorder(root->left,res);
        postorder(root->right,res);
        res.push_back(root->val);
    }
    vector postorderTraversal(TreeNode* root) {
        vector res;
        postorder(root,res);
        return res;
    }
};

迭代(自己写的）：

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector res;
        if(!root) return {};
        stack st;
        st.push(root);
        map m;
        while(!st.empty())
        {
            while(st.top() && !(m[root->left]==1 && m[root->right]==1))
            {
                root=st.top();
                st.push(root->right);
                st.push(root->left);
            }
            while(st.top()==nullptr)
            {
                m[st.top()]=1;
                st.pop();
            }
            root=st.top();
            if(m[root->left]==1 && m[root->right]==1)
            {
                st.pop();
                res.push_back(root->val);
                m[root]=1;
            }
        }
        return res;
    }
};

迭代（官解）

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

迭代（另一种写法）

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector res;
        if(!root) return {};
        stack st;
        st.push(root);
        map m;
        while(!st.empty())
        {
            root=st.top();
            if((!root->left && !root->right) || m[root])
            {
                st.pop();
                res.push_back(root->val);
                continue;
            }
            if(root->right) st.push(root->right);
            if(root->left) st.push(root->left);
            m[root]=1;
        }
        return res;
    }
};