Minimum distance between nodes in binary search tree (Question Number 783)

The title

Given the root node of a binary search tree, root, returns the minimum difference between the values of any two different nodes in the tree.

530: leetcode-cn.com/problems/mi… The same

Example 1:

Input: root = [4,2,6,1,3] output: 1Copy the code

Example 2:

Input: root = [1,0,48,null,null,12,49] output: 1Copy the code

Tip:

  • The number of nodes in the tree is in range[2, 100] 内
  • 0 <= Node.val <= 105

link

Leetcode-cn.com/problems/mi…

explain

This one, this one is not even thinking about the point.

Let’s look at the problem first, it’s a binary search tree, as long as we take the values of all the nodes of the binary search tree, sort them, and then loop through the array, take the difference between the two adjacent numbers, and get the minimum.

The key is how to take the value of all nodes, I think very simple, no matter what the traversal method, get all the nodes after the value of a sort of line, in fact, it is not.

Since it is a binary search tree, as long as the order traversal is carried out, the results are arranged in the order from smallest to largest. At this time, the difference comparison can be carried out.

Originally this question tests is in order traversal, that says in order traversal, this question is simple.

Your own answer (violent solution)

var minDiffInBST = function(root) {
  var arr = [root]
      nums = []
      min = Number.MAX_SAFE_INTEGER
  while (arr.length) {
    var item = arr.shift()
    nums.push(item.val)
    item.left && arr.push(item.left)
    item.right && arr.push(item.right)
  }
  nums.sort((a, b) => a- b)
  for (let i = nums.length - 1; i > 0; i--) {
    min = Math.min(nums[i] - nums[i - 1], min)    
  }
  return min
};
Copy the code

I’m just going to go through it, get all the values of the binary tree, sort it, sort it and loop it to get the minimum difference.

I missed the point completely.

A better approach (in order-traversal)

Since it is in order traversal, first talk about traversal method 👇 :

var minDiffInBST = function(root) { var stack = [] prv = Number.MIN_SAFE_INTEGER min = Number.MAX_SAFE_INTEGER while (root || stack.length) { while (root) { stack.push(root) root = root.left } root = stack.pop() min = Math.min(root.val -  prv, min) prv = root.val root = root.right } return min };Copy the code

The code for traversal is very simple. You need a stack to store the root array, and then you start the traversal.

So we start with the outer traversal, and in the outer traversal, the first thing we do is we do the inner traversal.

If root exists, then root is parsed. In the inner traversal, root is first pushed into the stack, then the left subtree of root is fetched, then the left subtree of root is pushed into the stack, and so on until root is null.

Once root is processed, the actual contents of the outer loop can be started. First, root is assigned to the last element in the stack. In this case, root’s val is the value that should be taken in the traversal, so compare and assign at this point.

When you’re done, you assign root to its right subtree and complete the loop.

And then we’re done, so the result of the traversal is the middle order traversal, which is relatively simple, if you don’t understand it, just memorize it, and there’s not a lot of code.

A better approach (in order-recursion)

The recursive approach is easier to understand than traversal and feels simpler 👇 :

var minDiffInBST = function(root) { var prv = Number.MIN_SAFE_INTEGER min = Number.MAX_SAFE_INTEGER function inorder(root) { if (! root) return inorder(root.left) min = Math.min(root.val - prv, min) prv = root.val inorder(root.right) } inorder(root) return min };Copy the code

PRV and min, not to mention, for this particular variable.

The in-order traversal of a recursion starts with a function called inorder. If root does not exist, return root. If so, perform a recursive operation on the left subtree — inorder(root.left), and then process and compare the val of root. When you’re done, you recurse to the right subtree of root, and that’s it.

The logic is really simple, you do a recursive operation on each node, and if you have a left subtree you do the left subtree first, then you do the current node, and then you do the right subtree last, it’s not too simple.

Better approach (middle order -Morris)

This method is a bit convoluted, the author really can not understand, later in the colleague’s explanation to barely understand, it took nearly 4 hours, here let go of the official answer, later will be a separate article to explain Morris traversal.

Official address: leetcode-cn.com/problems/bi…




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