Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/255.html

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

 

Example 1:

Input: preorder = [5,2,1,3,6]
Output: true

Example 2:

Input: preorder = [5,2,6,1,3]
Output: false

 

Constraints:

  • 1 <= preorder.length <= 104
  • 1 <= preorder[i] <= 104
  • All the elements of preorder are unique.

 

Follow up: Could you do it using only constant space complexity?

Algorithm

First set a minimum value low, then traverse the array, if the current value is less than the minimum value low, return false.

For the root node, push it onto the stack, and then traverse back,

If the number encountered is smaller than the element at the top of the stack, it means that it is the point of its left subtree and continues to be pushed onto the stack.

Until the number encountered is greater than the top element of the stack, then it is the value on the right child. You need to find the right subtree of which node,

So update the low value and delete the top element of the stack, and then continue to compare with the next top element,

If it is still greater than, continue to update the low value and delete the top of the stack, until the stack is empty or the current stack top element is greater than the current value, stop, push the current value,

In this way, if it does not return false before traversing the entire array, return true at the end.

Code

  • import java.util.Stack;
    
    public class Verify_Preorder_Sequence_in_Binary_Search_Tree {
    
        public static void main(String[] args) {
            Verify_Preorder_Sequence_in_Binary_Search_Tree out = new Verify_Preorder_Sequence_in_Binary_Search_Tree();
            Solution_dfs s = out.new Solution_dfs();
    
            System.out.println(s.verifyPreorder(new int[]{5,2,6,1,3}));
            System.out.println(s.verifyPreorder(new int[]{5,2,1,3,6}));
    
    
            Solution sss = out.new Solution();
    
            System.out.println(sss.verifyPreorder(new int[]{5,2,6,1,3}));
            System.out.println(sss.verifyPreorder(new int[]{5,2,1,3,6}));
        }
    
    
        public class Solution {
            public boolean verifyPreorder(int[] preorder) {
                int lowBound = Integer.MIN_VALUE;
                Stack<Integer> sk = new Stack<>();
                for (int each : preorder) {
                    if (each < lowBound) {
                        return false;
                    }
    
                    while (!sk.empty() && each > sk.peek()) { // s>peek => right value
                        lowBound = sk.pop();
                    }
                    sk.push(each);
                }
                return true;
            }
        }
    
    
        public class Solution_dfs {
            public boolean verifyPreorder(int[] preorder) {
                return dfs(preorder, 0, preorder.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            }
    
            boolean dfs(int[] preorder, int start, int end, int lower, int upper) {
                if (start > end) return true;
    
                int val = preorder[start];
                if (val <= lower || val >= upper) return false;
    
                int i = 0;
                for (i = start + 1; i <= end; ++i) {
                    if (preorder[i] >= val) break; // @note: i stops at root's first right child, same as above "if (each < lowBound) {"
                }
    
                return dfs(preorder, start + 1, i - 1, lower, val) && dfs(preorder, i, end, val, upper);
            }
    
        }
    }
    
    ############
    
    class Solution {
        public boolean verifyPreorder(int[] preorder) {
            Deque<Integer> stk = new ArrayDeque<>();
            int last = Integer.MIN_VALUE;
            for (int x : preorder) {
                if (x < last) {
                    return false;
                }
                while (!stk.isEmpty() && stk.peek() < x) {
                    last = stk.poll();
                }
                stk.push(x);
            }
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        bool verifyPreorder(vector<int>& A) {
            stack<int> s;
            int mn = INT_MIN;
            for (int n : A) {
                if (n < mn) return false;
                while (s.size() && s.top() < n) {
                    mn = s.top();
                    s.pop();
                }
                s.push(n);
            }
            return true;
        }
    };
    
  • class Solution:
        def verifyPreorder(self, preorder: List[int]) -> bool:
            stk = []
            last = -inf
            for x in preorder:
                if x < last:
                    return False
                while stk and stk[-1] < x:
                    last = stk.pop()
                stk.append(x)
            return True
    
    
    class Solution:  # o(N) but modifying input list
        def verifyPreorder(self, preorder: List[int]) -> bool:
            low = -math.inf
            i = -1
    
            for p in preorder:
                if p < low:
                    return False
                while i >= 0 and preorder[i] < p:
                    low = preorder[i]
                    i -= 1
                i += 1
                preorder[i] = p
    
            return True
    
    ############
    
    class Solution(object):
    
      # O(n) sapce complexity, **stack**
      def verifyPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: bool
        """
        if len(preorder) <= 1:
          return True
        stack, lastElem = [preorder[0]], None
        for i in range(1, len(preorder)):
          if lastElem > preorder[i]:
            return False
          while len(stack) > 0 and preorder[i] > stack[-1]:
            lastElem = stack.pop()
          stack.append(preorder[i])
    
        return True
    
    
  • func verifyPreorder(preorder []int) bool {
    	var stk []int
    	last := math.MinInt32
    	for _, x := range preorder {
    		if x < last {
    			return false
    		}
    		for len(stk) > 0 && stk[len(stk)-1] < x {
    			last = stk[len(stk)-1]
    			stk = stk[0 : len(stk)-1]
    		}
    		stk = append(stk, x)
    	}
    	return true
    }
    

All Problems

All Solutions