The title

Given an array of integers, you need to verify that it is the correct preemptive traversal sequence of a binary search tree. You can assume that the numbers in the sequence are not the same. Consider the following binary search tree:

     5
    / \
   2   6
  / \
 1   3
Copy the code

The sample

Example 1:

Input: [5,2,6,1,3] output: false

Example 2:

Input: [5,2,1,3,6] output: true

Answer key

Binary search tree

First we should know what a binary search tree is. A Binary Search Tree is either an empty Tree or a Binary Tree with the following properties: ** If the left subtree is not empty, the values of all nodes in the left subtree are less than the values of the root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively. ** Binary search tree, as a classical data structure, has both the characteristics of fast insertion and deletion of linked list and the advantages of fast search of array. Therefore, it is widely used, for example, in file system and database system, this data structure is generally used for efficient sorting and retrieval operations. In simple terms, a binary search tree is a binary tree with the following characteristics: it is either an empty tree, or a binary tree with the following properties: if its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively.

The former sequence traversal

Preorder traversal is also called preorder traversal, preorder traversal, can be written as the root left and right (binary tree parent node down first left and then right). The root is accessed first and then the left subtree is traversed, and then the right subtree is traversed. When traversing the left and right subtrees, the root is still visited, the left subtree is traversed, and the right subtree is traversed, returning if the binary tree is empty.

Their thinking

Because binary search tree has “left subtree all node values are less than the value of its root node, all right child the tree node values were greater than the value of its root node” this feature, so we can start from this characteristic, if you can find the left subtree or right subtree is greater than the root node is less than the value of the root node, then the array queue does not meet the characteristics of binary search trees.

code

/ * * *@param {number[]} preorder
 * @return {boolean}* /
var verifyPreorder = function(preorder) {
    let q = [],flag = -Infinity;
    for(let p of preorder){
    	// If the value is less than p, it can be judged as the left subtree node and root node of the current subtree. Pop them up. Flag should be the minimum value of the current array
        while(q.length && q[0] < p) flag = q.shift();
        // If flag is greater than p, the left subtree node is greater than the right subtree node, which does not meet the characteristics of binary search trees, so it should be false
        if(flag > p) return false;
        q.unshift(p);
    }
    return true;
};
Copy the code

Source: LeetCode

Link: leetcode-cn.com/problems/ve… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.