Kiểm tra Cây tìm kiếm nhị phân không có giá trị trong JavaScript

Cây tìm kiếm nhị phân không định giá

Cây tìm kiếm nhị phân không có giá trị nếu mọi nút trong cây có cùng giá trị.

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy gốc của BST và trả về true nếu và chỉ khi cây đã cho là không có giá trị, ngược lại là false.

Ví dụ:nếu các nút của cây -

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

Sau đó, đầu ra phải là -

const output = false;

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

false