เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับรูทของ BST ที่เก็บข้อมูลตัวเลขบางอย่างเช่นนี้ -
1 \ 3 / 2
ฟังก์ชันควรคืนค่าความแตกต่างสัมบูรณ์ขั้นต่ำระหว่างสองโหนดของทรี
ตัวอย่างเช่น −
สำหรับแผนผังด้านบน ผลลัพธ์ควรเป็น −
const output = 1;
เพราะ |1 - 2| =|3 - 2| =1
ตัวอย่าง
รหัสสำหรับสิ่งนี้จะเป็น −
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ // root of a binary seach tree this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,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