leetcode
January 22, 2024

Viiisit [LeetCode] - 530. Minimum Absolute Difference in BST

#php#javascript#ruby

keep learning, keep coding!

Problem - Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

翻譯蒟蒻

找到樹中兩個值之間最接近的差異是多少。

Binary Search Tree (BST) 二元搜索樹是一種二元樹，其中每個節點的左子樹中的值都小於該節點的值，而右子樹中的值都大於該節點的值。這種樹的結構有助於快速查找和比較。

Solution - JavaScript

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 {number}
 */
var getMinimumDifference = function(root) {
  let min = Infinity
  // // 初始化一個陣列 prev，用於存儲前一個訪問的節點的值
  let prev = []
  const inorder = (root) => {
    if (!root) return
    inorder(root.left)
    if (prev.length) {
      // 比較當前節點值與前一節點值的差值，取最小值
      min = Math.min(min, root.val - prev[0])
    }
    prev[0] = root.val
    inorder(root.right)
  }
  inorder(root)
  return min
}

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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 {number}
 */
var getMinimumDifference = function(root) {
  let min = null;
  let prev = null;
  let stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    if (prev) {
      min = min === null ? curr.val - prev.val : Math.min(min, curr.val - prev.val);
    }
    prev = curr;
    curr = curr.right;
  }
  return min;
}

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def get_minimum_difference(root)
  min = nil
  prev = nil
  stack = []
  node = root 
  while !node.nil? || !stack.empty?
    while !node.nil?
      stack << node
      node = node.left
    end
    node = stack.pop
    if prev.nil?
      prev = node.val
    else
      min = [min, node.val - prev].compact.min
      prev = node.val
    end
    node = node.right
  end
  min
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function getMinimumDifference($root) {
  $min = null;
  $prev = null;
  $stack = [];
  $node = $root;
  while ($node || $stack) {
    while ($node) {
      array_push($stack, $node);
      $node = $node->left;
    }
    $node = array_pop($stack);
    if ($prev !== null) {
      $min = $min === null ? $node->val - $prev : min($min, $node->val - $prev);
    }
    $prev = $node->val;
    $node = $node->right;
  }
  return $min;
}

LeetCode 傳送門 - Minimum Absolute Difference in BST