preface

I have already brushed nearly 20 questions and dreamed up ideas out of thin air without thinking about the experience summed up in the previous few questions. So I think I should stop and review the previous problems, sort out the routine of doing the problems. Consider the old and learn the new.

After the sequence traversal definition: [left subtree | | right sub tree root node], namely traversal sequence is “left, right, root”.

Binary search tree definition: the value of all nodes in the left subtree < the value of the root node; Values of all nodes in the right subtree > values of the root node; The left and right subtrees are binary search trees respectively.

Topic describes

Enter an array of integers to determine if the array is the result of a sequential traversal of a binary search tree. Returns true if it is, false otherwise. Suppose that any two numbers in the input array are different.

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

Example 1:

Input:1.6.3.2.5] output:false
Copy the code

Example 2:

Input:1.3.2.6.5] output:true
Copy the code

Their thinking

  1. By the nature of a binary search tree, the value of the node in the left subtree is less than the value of the root node, and the value of the right subtree is opposite
  2. Therefore, based on the value of the current root node, search for the subscript that appears on the first right child node. In the previous step, the left subtree already meets the requirement
  3. Therefore, determine whether the size of the right subtree meets the condition. If both conditions are met, it means that the properties of the binary search tree of the current root meet. Then, we recursively judge whether the left and right subtrees meet the condition

AC code

var verifyPostorder = function(postorder) {
    let len = postorder.length;
    if(len <2) return true; // Only one element must be traversed backwards
    let root = postorder[len-1];// The last element of the sequence traversal is the root node
    let i = 0;
    for(; i < len -1; i++) {
        if(postorder[i] > root){// is the right subtree of root
            break; }}// Check whether the left subtrees are all smaller than root
    let result = postorder.slice(i, len - 1).every(item= > item > root);
    if(result){ // Perform recursion to determine whether the left and right subtrees of root satisfy binary tree properties.
        return verifyPostorder(postorder.slice(0,i)) && verifyPostorder(postorder.slice(i,len-1))}else {
        return false; }};Copy the code

Conclusion:

Binary search tree definition: the value of all nodes in the left subtree < the value of the root node; Values of all nodes in the right subtree > values of the root node; The left and right subtrees are binary search trees respectively. This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign