Kiểm tra cây BST đơn giá trị trong JavaScript

Cây BST đơn giá trị (Univalued BST)

Một cây tìm kiếm nhị phân là đơn giá trị nếu mọi nút trong cây đều có cùng giá trị.

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào gốc của BST, trả về true nếu và chỉ nếu cây là đơn giá trị, ngược lại false.

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

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

Thì đầu ra nên là:

const output = false;

Ví dụ minh họa

Mã thực hiện (đệ quy):

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

Đầu ra

Kết quả trong console sẽ là:

false