C++ O(N) time O(1) space (in-place stack)


  • 2
    Q

    This problem is very interesting. Recursive approach is very straightforward, though solution is likely of O(nlogn)/O(logn) time/space complexity (avg), or O(N^2)/O(N) worst case.

    The key to optimize is to recall how iterative(non-recursive) pre-order traversal works, then follow the same idea to "reconstruct" BST from preorder sequence, during which we need a stack to keep track of node path from root. The trick here is to use input preorder sequence to simulate the stack in-place. For verification purpose, we need to maintain a "lower bound" variable: when we visit a node that is the right child of its parent, the parent's value must be lower bound of all subsequent values.

       class Solution {
        public:
            bool verifyPreorder(vector<int>& preorder) {
                if (preorder.empty()) return true;
                int lowerBound = INT_MIN;
                int stackTopPosition = 0;
                for (int pos = 1; pos < preorder.size(); ++pos) {
                    if (preorder[pos] < lowerBound) return false;
                    while (stackTopPosition >= 0 && preorder[pos] > preorder[stackTopPosition]) {
                        lowerBound = preorder[stackTopPosition--];  // Update 
                    }
                    preorder[++stackTopPosition] = preorder[pos];  // Push to stack
                }
                return true;
            }
        };

Log in to reply
 

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