4ms Java O(n) Time and O(1) Space, no recursion or changing value


  • -1
    A

    We know that in BST every node in right subtree must be larger than the root and less than the root's root.

    Thus, we can set the root's value as floor and the root's root's value as the ceiling. Once a value in right subtree is less than the floor, we know that it is not a BST. Once a node in the right tree has a value larger than the ceiling, we know that the current node belongs to another right subtree.

    Then we represent the ceiling as preorder[l], the current node as preorder[r]. Once preoder[r] is larger than preorder[l], we know that the subtree r used to be iterating inside is over. Then we set a new floor and a new ceiling. The ceiling can be the node l 's root, which is represented as l--.

    If we find that l<0, we know that the interval between l and r is a BST. Then we can just take r as a new root and check if it's a BST. I use the variance 'leftmost' to represent that we don't need to examine the value left to the leftmost.

    In this way, we don't need more space or recursion.

    My first post. Hope it helps.

    ···
    class Solution {
    public boolean verifyPreorder(int[] preorder) {
    if(preorder.length<2)return true;
    int l=0,r=1,len=preorder.length,floor=preorder[0],leftmost=0;

        //find the least value
        while(r<len){
            if(preorder[l]>preorder[r]){
                l++;
                r++;
            }
            else break;
        }
        //set the least value
        floor=preorder[l];
        
        //if there is a root with smaller value, set the left node value as floor
        if(l>leftmost)l--;
        //if there are no roots with smaller value in the tree, set the current biggest node as toppest
        else{
            l=r;
            leftmost=l;
            r++;
        }
        
        while(r<len){
            //the right node's value cannot be less than the floor
            //when right node breaks the ceiling and we would set the former ceiling as a new floor
            while(r<len&&preorder[r]<preorder[l]){
                if(preorder[r]<=floor)return false;
                r++;
                
            }
            floor=preorder[l];
            
            //if there is a root with smaller value, set the left node value as floor
            if(l>leftmost){
                l--;
            }
            //if there are no smaller root in the tree, set the current biggest node as toppest
            else{
                l=r;
                leftmost=l;
                r++;
            }
        }
        
        
        return true;
    }
    

    }
    ···


  • 0
    M

    It's wrong. It for example fails [0, 4, 2, 3, 1], incorrectly returning true.

    Btw, please format your code properly, otherwise it's unnecessarily hard to read and copy&paste for testing.


Log in to reply
 

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