C++ 6-7 lines O(n) rumtime with O(1) space solution for both preorder and postorder


  • 1

    A regular O(n) solution for preorder using a stack:

    bool verifyPreorder(vector<int>& preorder) {
            stack<int> st;
            for (int lower = INT_MIN, i = 0; i < preorder.size(); i++) {
                if (lower >= preorder[i]) { return false; }
                while (st.size() && st.top() < preorder[i]) { lower = st.top(); st.pop(); }
                st.push(preorder[i]);
            }
            return true;
    }
    

    O(1) space for preorder (do it in place):

        bool verifyPreorder(vector<int>& preorder) {
            // using preorder itself as stack, k is the current stack top position
            for (int lower = INT_MIN, k = -1, i = 0; i < preorder.size(); i++) {
                if (preorder[i] < lower) { return false; }
                while (k >= 0 && preorder[k] < preorder[i]) { lower = preorder[k--]; }
                preorder[++k] = preorder[i];
            }
            
            return true;
    }
    

    O(1) space for postorder (do it in place). I scanned the array right to left to make it kind of "reversed" preorder:

        bool verifyPostorder(vector<int>& postorder) {
            // using postorder itself as stack, k is the current stack top position
            for (int upper = INT_MAX, k = postorder.size(), i = postorder.size() - 1; i >= 0; i--) {
                if (postorder[i] > upper) { return false; }
                while (k < postorder.size() && postorder[k] > postorder[i]) { upper = postorder[k++]; }
                postorder[--k] = postorder[i];
            }
            
            return true;
    }
    

  • 0

    You changed the input data which is passed by reference. I don't think it is a good idea.


Log in to reply
 

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