My C++ Iterative Solution ,Easy to understand


  • 0

    Firstly , I use pair<TreeNode,bool> to stored the TreeNode status.
    If bool = true , We just completed travel of left subtree.
    if bool = false , We completed the traversal of this TreeNode

    class Solution {
    /***
     * 迭代版本,需要为根节点多提供一个flag信息,表示这个点右子树是否已经被访问过
     * 
     * 首先while循环寻找到最深的左子节点,
     * 这时候会有两个选择
     * 1. st.top()右子树没有被访问过,访问右子树
     * 2. st.top()右子树已经被访问,push val进vector中
     * 同时pop出st的节点,另root = nullptr(给下一次循环使用)
     * 
     */
    stack<pair<TreeNode* , bool>> st;
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> res;
            while(!st.empty()||root){
                while(root){
                    st.emplace(root,true);
                    root = root->left;
                }
                if(st.top().second){ //travel its rightTree
                    root = st.top().first;
                    st.top().second = false;
                    root = root->right;
                }
                else{  //complete travel,and pop()
                    root = st.top().first;
                    res.push_back(root->val);
                    st.pop();
                    root = nullptr;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.