กำลังตรวจสอบแผนผังการค้นหาไบนารีที่ไม่มีค่าใน JavaScript

แผนผังการค้นหาไบนารีที่ไม่มีค่า

ต้นไม้การค้นหาแบบไบนารีจะไม่มีค่าถ้าทุกโหนดในทรีมีค่าเท่ากัน

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับรูทของ BST และคืนค่า จริง ถ้าและต่อเมื่อทรีที่กำหนดไม่มีค่า มิฉะนั้น จะเป็นเท็จ

ตัวอย่างเช่น ถ้าโหนดของต้นไม้คือ −

const input = [5, 5, 5, 3, 5, 6];

จากนั้นผลลัพธ์ควรเป็น −

const output = false;

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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(5);
BST.insert(5);
BST.insert(5);
BST.insert(3);
BST.insert(5);
BST.insert(6);
const isUnivalued = (root) => {
   const helper = (node, prev) => {
      if (!node) {
         return true
      }
      if (node.data !== prev) {
         return false
      }
      let isLeftValid = true
      let isRightValid = true
      if (node.left) {
         isLeftValid = helper(node.left, prev)
      }
      if (isLeftValid && node.right) {
         isRightValid = helper(node.right, prev)
      }
      return isLeftValid && isRightValid
   }
   if (!root) {
      return true
   }
   return helper(root, root.data)
};
console.log(isUnivalued(BST.root));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

false