Nuggets team number online, help you Offer rimmon! Click to see details

Verify binary search tree (Question number 98)

The title

Given a binary tree, judge whether it is a valid binary search tree.

Suppose a binary search tree has the following characteristics:

  • The left subtree of a node contains only the number smaller than the current node.
  • The right subtree of a node contains only the number greater than the current node.
  • All left and right subtrees must themselves also be binary search trees.

Example 1:

Input: 2 / \ 1 3 Output: trueCopy the code

Example 2:

Input: 5 / \ 1 4 / \ 3 6 Output: false Description: Input: [5,1,4, NULL, NULL,3,6]. The root node has a value of 5, but its right child node has a value of 4.Copy the code

link

Leetcode-cn.com/problems/va…

explain

This brings us to the basic definition of a binary search tree, which is simple: all the left subtrees must be smaller than the current node, and all the right subtrees must be larger than the current node. Note that the definition here is all values, not limited to one level.

Have no idea at the beginning, this is the first time around have encountered the situation, without what good idea about how to traverse, subsequent it then turns out that the iterative method is very simple, but only in sequence traversal as answers to traverse, this let me a little surprised, thought there will be a normal traversal method, but look for a long time also have found, a little strange.

Your own answer (recursion)

👇 is the author’s problem solving process.

First, I quickly write an answer, using the characteristics of binary search trees, the value of the left node will be less than the current node, the value of the right node will be greater than the current node, and then a wave of traversal:

var isValidBST = function(root) { if (! root) return true if (root.left && root.left.val > root.val) { return false } if (root.right && root.right.val < root.val) { return false } return isValidBST(root.left) && isValidBST(root.right) };Copy the code

Look very simple, the main is to determine the left and right node value and the current node value of the relationship, and then a submission, in place GG.

The problem here is simple, because the size relationship of binary search tree is not limited to a certain level, their size relationship exists in the whole tree, that is, the value of the top node must be greater than the value of all left child nodes, and less than the value of all right child nodes.

The isValidBST method requires two more parameters, which are passed to the left and right child nodes to maintain the size of the tree. And each level changes, so dynamic assignments are required.

The idea here is also relatively simple. If it is a left subtree, then its node value must be greater than a minimum value, which is actually the value of the current node. The same is true for the right subtree.

var isValidBST = function(root, max = Number.MAX_SAFE_INTEGER, min = Number.MIN_SAFE_INTEGER) { if (! root) return true if (root.left && (root.left.val >= root.val || root.left.val <= min)) { return false } if (root.right && (root.right.val <= root.val || root.right.val >= max)) { return false } return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val) };Copy the code

And then you run again, and it works, but it’s not really the best recursive solution.

A better way (recursion)

var isValidBST = function(root) { function checkNode(node, max, min) { if (! node) return true if (node.val <= min || node.val >= max) return false return checkNode(node.left, node.val, min) && checkNode(node.right, max, node.val) } return checkNode(root, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER) };Copy the code

In my own answer, I judge the value of the left subtree and the right subtree of the current node, which is a little more complicated.

Here, we only need to judge the relationship between the value of the current node and Max and min. The value of the current node must be greater than the minimum value and less than the maximum value. Otherwise, the size relationship of the whole tree cannot be maintained.

The assignment of Max and min is also simple, and the initialization is simple, because it is a top-level node, so there are no restrictions, just passing in the maximum and minimum values that JavaScript will accept.

After that, if it’s the left subtree, then the maximum value is the value of the current node, and the minimum value doesn’t matter, just use the minimum number in JavaScript; If it is a right subtree, then the maximum value is ignored and the minimum value is the value of the current node.

If you want to write this answer, you have to understand binary search trees very thoroughly, otherwise you have to write the answer like I did, but it’s still a little redundant, it’s not very well understood.

PS: You can also condense the code to a single line here.

var isValidBST = function(root, max = Number.MAX_SAFE_INTEGER, min = Number.MIN_SAFE_INTEGER) { return ! root || root.val < max && root.val > min && isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val) };Copy the code

A Better Approach (iteration)

var isValidBST = function (root) { var stack = [] inorder = Number.MIN_SAFE_INTEGER while (stack.length || root) { while  (root) { stack.push(root) root = root.left } root = stack.pop() if (root.val <= inorder) return false inorder = root.val root = root.right } return true };Copy the code

The code isn’t long, but it’s a little hard to understand. We define two variables: stack, which holds the node value, and inorder, which holds the current data.

Here to say a characteristic of order traversal, that is, the result of traversal must be from small to large, if there is a value smaller than the previous one, it proves that this number is not a binary search tree, the specific logic can see the following GIF.

So let’s get back to the point where we’ve identified two variables and we’re going to start iterating, and we’re going to make sure that stack is not an empty array and that root is not null, otherwise we’re done. Then you iterate through root, unpack root, take all of its left nodes, and store them in the stack.

Then take out the stored node information from the stack, determine whether the current node val is greater than inorder, if not directly return false, otherwise assign val to inorder, then get the right node, start a new round of traversal.

In this way, the result will be obtained when the traversal is complete.

Here is really very difficult to understand, anyway, the author is to think about more than half an hour to understand, may be relatively stupid, think well, always can understand.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ