ค้นหาความแตกต่างสัมบูรณ์ขั้นต่ำภายในแผนผังการค้นหาแบบไบนารีใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน 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