ปัญหา
ได้รับรากของ BST ที่เก็บตัวเลข ให้หาความต่างสัมบูรณ์น้อยที่สุดระหว่างโหนดใดๆ สองโหนด
ตัวอย่าง
BST: 1 \ 3 / 2
ผลลัพธ์: 1 (เพราะ |1-2| = |3-2| = 1)
โค้ดตัวอย่าง
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; } };
class BinarySearchTree{
constructor(){ this.root = null; }
insert(data){ ... }
insertNode(node, newNode){ ... }
}
const BST = new BinarySearchTree();
BST.insert(1); BST.insert(3); BST.insert(2);
const getMinimumDifference = function(root) {
const nodes = [];
const dfs = (root) => {
if(root) { dfs(root.left); nodes.push(root.data); dfs(root.right); }
};
dfs(root);
let result = nodes[1] - nodes[0];
for(let i = 1; i < nodes.length - 1; i++) {
result = Math.min(result, nodes[i + 1] - nodes[i]);
}
return result;
};
console.log(getMinimumDifference(BST.root));
ผลลัพธ์
1
