72ms c++ solution using one stack, O(n) time and space


  • 17
    Y

    The idea is traversing the preorder list and using a stack to store all predecessors. curr_p is a predecessor of current node and current node is in the right subtree of curr_p.

    For example, for the following bst with preorder 6,3,1,2,5,4,7:

                  6
                /  \  
               3    7
              /  \
             1   5
             \   /
             2  4   
    

    We push to stack before we see 2. So at 2 the stack is 6,3,1. For 2, we pop stack until we see 3 which is greater than 2 and curr_p is 1. 2 is in left subtree of 3 and is right child of 1. Stack is 6,3,2 now. Then we see 5, and we pop stack until 6 and curr_p is 3. Stack now is 6,5. Then we see 4 and push to stack. At 7, we pop stack until empty and curr_p is 6.

    bool verifyPreorder(vector<int>& preorder){
        // using stack
        int sz = preorder.size();
        if(sz < 2) return true;
        stack<int> s;
        s.push(preorder[0]);
        int curr_p = INT_MIN;
        for(int i=1; i<sz; i++){ 
            if(s.empty() || preorder[i]<s.top()){ // if current node is less than stack top, then go to left subtree
                if(preorder[i]<curr_p) return false; 
                s.push(preorder[i]);
            }
            else{
                while(!s.empty() && s.top()<preorder[i]){ //find curr_p such that current node is right child of curr_p
                    curr_p = s.top();
                    s.pop();
                }
                s.push(preorder[i]);
            }
        }
        return true;
    }

  • 0
    F

    Good explanation, great job!


  • 0
    L

    Compare to most voted one, this code is not fully optimized, but I think it is easier to understand!


  • 1

    I think there is no need to make the first element special

    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if (preorder.size() < 2) return true;
    
            stack<int> s;
            int curNum = INT_MIN; // mark the number has been counted
    
            for (int i = 0; i < preorder.size(); i++) {
                if (s.empty() || s.top() > preorder[i]) {
                    if (curNum > preorder[i]) return false;
                    s.push(preorder[i]);
                } else {
                    while (!s.empty() && s.top() < preorder[i]) {
                        curNum = s.top();
                        s.pop();
                    }
                    s.push(preorder[i]);
                }
            }
            return true;
        }
    };
    
    

  • 0
    X

    share my simpler code

    class Solution {
    public:
        bool verifyPreorder(vector<int> &preorder) {
            stack<int> s;
            long prev = LONG_MIN;
    
            for (const int &e : preorder) {
                while (!s.empty() && e >= s.top()) {
                    prev = s.top();
                    s.pop();
                }
                if (e <= prev) {
                    return false;
                }
                s.push(e);
            }
            return true;
        }
    };
    
    
    

  • 1
    W

    @yu23 Share my solution without using an explicit stack, we can use the input vector as the stack : )

    bool verifyPreorder(vector<int>& preorder) {
            stack<int> stk;
            int lb = INT_MIN, stkTop = -1;
            for(int i = 0; i < preorder.size(); i++) {
                if(preorder[i] <= lb) return false;
                while(stkTop >= 0 && preorder[stkTop] < preorder[i]) {
                    lb = preorder[stkTop];
                    stkTop--;
                } 
                preorder[++stkTop] = preorder[i];
            }
            return true;
        }
    

Log in to reply
 

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