current position:Home>[javascript question brushing] tree - verify binary search tree, leetcode 98

[javascript question brushing] tree - verify binary search tree, leetcode 98

2022-06-24 08:51:11GoldenaArcher

[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 :

example1

example2

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

1
3
5
6
7

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 3 < 5 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 ⁡ 5 < 6 < \inf 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 5 < 3 < 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 A A All the left subtrees of are less than A A A Value , And all A A A All right subtrees of are greater than A A 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);
};

copyright notice
author[GoldenaArcher],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/175/202206240636210350.html

Random recommended