52ms (94.48%) C++ neat&fast solution with explanation-- 1-line recursion


  • 0

    Many previous posts provide pretty awesome explanation how to verify a valid preorder sequence. Here I am trying to give a different thought: explore longest valid preorder subsequence, and return true if the result is the entire array.

    The time complexity is O(n), and memory is O(h), where h is the height of the BST.

    Here is the code:

        bool verifyPreorder(vector<int>& preorder) {
            return vp(preorder.begin(),preorder.end(),INT_MIN-1ll,INT_MAX+1ll) == preorder.end();
        }
        typedef vector<int>::const_iterator Iter; //for readability
        Iter vp(Iter b, Iter e, long long lo, long long hi) {
            return (b==e || *b <= lo || *b >= hi) ? b : vp(vp(b+1,e,lo,*b),e,*b,hi);
        }
    

    the function 'vp' return the upper bound (excluding) of sub-BST tree whose value ranges in (lo,hi).

    1. if the value is out of this range, then the node under check is not in the sub-BST. In this case, we return the current position (says, 'b') as the upper bound (excluding) of the subtree.
    2. Otherwise, the current element to check is part of sub BST; we check how far its left subtree goes(that is, vp(b+1,e,lo,*b)), and check how far its right subtree goes after the left subtree upper bound (that is, vp(vp(b+1,e,lo,*b),e,*b,hi) ).

    Oh, and the condition b==e is trivial : return end iterator if there is no more element to check.)

    By passing the whole array into the top recursive call, the range laying in preorder.begin() and the returned iterator is the longest subsequence.


Log in to reply
 

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