Java Solution. No stack and No change preorder values. O(n) time and O(1) space


  • 0
    V
    I don't know if my solution is a general one (I mean if you ask follow up questions like verify the postorder sequence or something). But it works for this one.
    Idea: 1 What's the current lower bound value ?
            if current value is smaller than current lower bound, return false.
          2 When does the current lower bound value change ?
            every time we jump from left branch to right branch.
            case 1: we jump from left to right but we still stay at global left
            case 2: we jump from left to right but we jump to the global right
    
    
    
       public boolean verifyPreorder(int[] preorder) {
            int l = preorder.length;
            if (l == 0) return true;
            
            int mark_min = Integer.MIN_VALUE;
            int mark_max = preorder[0];
            int pos = 1;
            
            while (pos < l) {
                while (pos < l && preorder[pos] < preorder[pos - 1]) {
                    if (preorder[pos] < mark_min) return false;
                    pos += 1;
                }
                
                if (pos < l) {
                    if (preorder[pos] > mark_max) {
                        mark_min = mark_max;
                        mark_max = preorder[pos];
                    } else {
                        mark_min = preorder[pos - 1];
                    }
                }
                
                pos += 1;
            }
            
            return true;
        }

  • 0
    C

    There is bug in your logic. e.g. for a non-BST such as [6,4,1,2,5,3] (look at the position of 4 and 3), your code judges it as true.

                ---- 6
              /
            4
        /       \
      1          5
       \         /
        2      3

  • 0
    V

    Thank you so much. Yes, u r right~ My code is wrong but it passes all the 59 test cases. We find a lost test case LOL~ I have contacted the admin to check it out. @1337c0d3r


  • 0

    Thanks! I have just added the test case.


Log in to reply
 

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