[JavaScript Brush problem ] Trees - Verify binary search tree , leetcode 98

github repo Address : https://github.com/GoldenaArcher/js_leetcode,Github The catalog of Probably It will be updated more diligently .

Title address ：98. Validate Binary Search Tree

subject

as follows ：

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Their thinking

The first requirement in the title is ：

The nodes contained in the left subtree Less than The value of the current node

The second requirement is ：

The nodes contained in the right subtree Greater than The value of the current node

So that's what I wrote when I first started using recursion ：

const validate = (root) => {
    
  if (!root) return true;

  if (root.val >= root?.left?.val || root.val <= root?.right?.val) return false;

  return validate(root.left) && validate(root.right);
};

This hierarchical search , From the two cases given in the title , This writing method can run through ：

however , Once this kind of writing encounters such a situation, there is no way to deal with it ：

The tree above is not a legal binary search tree , because 6 The left node of is 3, The binary search tree must satisfy that the value of the right subtree is greater than the current value .$3<5$, Naturally, there is no way to satisfy the conditions of binary search tree .

in other words , In recursive conditions , It is necessary to substitute a maximum value and a minimum value to judge whether the current node is within a reasonable range .

Take the tree above as an example , When calculating to the root node ; The judgment is as follows ：$ -\inf < 5 < \inf$, therefore 5 Is a legal value .

Into the second layer , The child node on the left is updated , Update the maximum value to the value of the parent node , We can draw $ -\inf < 1 < 5$, therefore 1 It's also a legal value . The judgment of the right node is $5<6<\inf$, It is also within the specified scope , First of all + The second layer satisfies a binary tree .

Into the third layer ,1 No child nodes , So it ends here . about 6 For the left subtree of , At this time, the minimum value is still maintained at 5, The maximum value is 6,$5<3<6$ This equation does not hold , So in this step you can go back to false 了 .

Use JavaScript Problem solving

Each step of the recursion calls the current low or high Pass it to the next floor , At the same time, the minimum value is updated when checking the right subtree , Update the maximum value when checking the left subtree , This will satisfy all $A$ All the left subtrees of are less than $A$ Value , And all $A$ All right subtrees of are greater than $A$ Value This demand .

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {boolean} */
var isValidBST = function (root) {
    
  const validate = (root, low, high) => {
    
    if (root === null) return true;

    if (
      (low !== null && root.val <= low) ||
      (high !== null && root.val >= high)
    )
      return false;

    return (
      validate(root.right, root.val, high) && validate(root.left, low, root.val)
    );
  };

  return validate(root, null, null);
};