Divide Conquer Java Solution


  • 18
    Q

    A BST's left child is always < root and right child is always > root.

    public boolean verifyPreorder(int[] preorder) {
        if(preorder == null || preorder.length == 0) return true;
        return verify(preorder, 0, preorder.length - 1);
    }
    
    private boolean verify(int[] a, int start, int end) {
        if(start >= end) return true;
        int pivot = a[start];
        int bigger = -1;
        for(int i = start + 1; i <= end; i++) {
            if(bigger == -1 && a[i] > pivot) bigger = i;
            if(bigger != -1 && a[i] < pivot) return false;
        }
        if(bigger == -1) {
            return verify(a, start + 1, end);
        } else {
            return verify(a, start + 1, bigger - 1) && verify(a, bigger, end);
        }
    }

  • 1

    Hi. qianzhige. Thanks for your sharing. Well, I think it is the most easy and simple idea. However, translating it into C++ gives the TLE...

    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            int n = preorder.size();
            return verify(preorder, 0, n - 1);
        }
    private:
        bool verify(vector<int>& preorder, int l, int r) {
            if (l >= r) return true;
            int pivot = preorder[l], m = -1;
            for (int i = l + 1; i <= r; i++) {
                if (m == -1 && preorder[i] > pivot) m = i;
                if (m != -1 && preorder[i] < pivot) return false;
            }
            if (m == -1) return verify(preorder, l + 1, r);
            return verify(preorder, l + 1, m - 1) && verify(preorder, m, r);
        }
    };
    

    Even I use int* instead of vector<int>, TLE still occurs...

    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            int n = preorder.size();
            int* p = new int[n];
            for (int i = 0; i < n; i++) p[i] = preorder[i];
            return verify(p, 0, n - 1);
        }
    private:
        bool verify(int* p, int l, int r) {
            if (l >= r) return true;
            int pivot = p[l], m = -1;
            for (int i = l + 1; i <= r; i++) {
                if (m == -1 && p[i] > pivot) m = i;
                if (m != -1 && p[i] < pivot) return false;
            }
            if (m == -1) return verify(p, l + 1, r);
            return verify(p, l + 1, m - 1) && verify(p, m, r);
        }
    };

  • 0

    The time complexity for this solution is O(n^2)


  • 0
    N

    my approach is similar. it passed, but almost TLE.

    class Solution {
    public:
    bool verifyPreorder(vector<int>& preorder) {
    return verify(preorder, 0, preorder.size()-1, INT_MIN, INT_MAX);
    }

    bool verify(vector<int>& preorder, int s, int e, int min, int max) {
        if (s > e) return true; 
        int r = preorder[s];
        if (!(r >= min && r <= max)) return false; 
        if (s==e) return true; 
        //pre-cond s<e
        int p; 
        for (p=s+1; p<=e && preorder[p] < r; ++p);
        
        if (verify(preorder, s+1, p-1, min, r) && verify(preorder, p, e, r, max))
            return true; 
        return false; 
    }
    

    };


  • 1
    D

    @qianzhige it looks like that this solution is O(nlogn) because T(n) = 2T(n/2) + n.


  • 3
    W

    @dachuan.huang +1. But the worst case will be O(N^2) when the tree looks like a descending single chain.


  • 0

    nice solution, same here and I believe the performance is O(NlogN) - each node is considered logN times, but I'm bit unclear on this, any thoughts. Thanks!

        public bool VerifyPreorder(int[] preorder) 
        {
            return IsPreOrder(preorder, 0, preorder.Length - 1, 0, 0, false, false);
        }
        
        public bool IsPreOrder(int[] arr, int left, int right, int min, int max, bool applyMin, bool applyMax)
        {
            if (left > right) return true;
            
            int root = arr[left];
            if ((applyMin && root < min) || (applyMax && root > max)) return false;
            
            int pos = left + 1;
            while (pos <= right && arr[pos] < root) pos++;
            
            return IsPreOrder(arr, left + 1, pos - 1, min, root, applyMin, true)
                    && IsPreOrder(arr, pos, right, root, max, true, applyMax);
        }
    

  • 0
    F

    Apart from stack of recursion, what is the space complexity here? I think it is average O(logn) and worst O(n). Since each recursion function's pivot and bigger will be kept until all sub-function are done. Correct me if I'm wrong.


  • 0
    F

    Same idea. Slow too. Have fun with it. lol

    class Solution {
        public boolean verifyPreorder(int[] preorder) {
            return helper(preorder, 0, preorder.length - 1);
        }
        public boolean helper(int[] preorder, int start, int end) {
            if (start >= end) {
                return true;
            }
            int root = preorder[start];
            int i = start + 1;
            while (i <= end){
                if (preorder[i] > root) {
                    break;
                }
                i++;
            }
            if (!valid(preorder, root, i, end)) {
                return false;
            }
            return helper(preorder, start + 1, i - 1) && helper(preorder, i, end);
        }
        public boolean valid(int[] preorder, int root, int start, int end) {
            if (start > end) {
                return true;
            }
            for (int i = start; i <= end; i++) {
                if (preorder[i] < root) {
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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