15ms Genuine O(1) Space Java Sol. Fast and Concise.


  • 0
    O

    l, r mean the allowed value border for p[i-1]'s sub-tree.

    If p[i] goes out of (l, r), go upward to find new (l, r), otherwise the binary search tree is illegal.

        public boolean verifyPreorder(int[] p) {
            int l = Integer.MIN_VALUE, r = Integer.MAX_VALUE;
            for (int i = 1; i < p.length; i++) {
                if (p[i] < l) return false;
                if (p[i] < r) {
                    if (p[i] < p[i - 1]) 
                        r = p[i - 1];
                    else
                        l = p[i - 1];
                } else {
                    int j;
                    for (j = i - 1; j >= 0 && p[j] < p[i]; j--)
                        l = Math.max(l, p[j]);
                    r = (j >= 0) ? p[j] : Integer.MAX_VALUE;
                }
            }
            return true;
        }
    

Log in to reply
 

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