Using binary search : C++ O(nlogn) neat solution -- only 4 lines of main logic


  • 0

    I believe a person who is willing to challenge this problem has mastered the basic problem: https://leetcode.com/problems/validate-binary-search-tree. Let's review the 1-line code solution for the validation:

        bool isValidBST(TreeNode* root, long long lo = INT_MIN-1ll, long long hi = INT_MAX+1ll) {
            return !root || root->val >lo && root->val < hi && isValidBST(root->left, lo, root->val) && isValidBST(root->right, root->val, hi);
        }
    

    My idea is to adopt the same strategy on this problem, plus binary search to help divide&conquer the problem.

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

    Yeah I know the array is not sorted, but the binary search still can split the array into 2 halves. If it is a valid preorder sequence, the left half should be in the range of lo and the root value.(I believe you know what happens to the other half.)

    In some sense, this solution disprove the preorder sequence is right by proving the binary search result is going wrong. :)


Log in to reply
 

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