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

2022-06-24 08:51:11

# [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 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 , 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 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 All the left subtrees of are less than A A Value , And all A A All right subtrees of are greater than 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);
};