A real Postorder Traversal .without reverse or insert, 4ms


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

  • 0

    Cool approach, that double pushing.


  • 0
    Y

    @heiswyd what is time-complexity of this solution? ( I guess 2*n, where n is number of nodes)


Log in to reply
 

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