ตรวจสอบ Binary Search Tree ที่มีค่าเดียว (Univalued) ใน JavaScript

Univalued Binary Search Tree

Binary Search Tree เป็น univalued ถ้าทุกโหนดในต้นไม้มีค่าเท่ากัน

ปัญหา

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

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

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(){
    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