在 JavaScript 中检查单值二叉搜索树
单值二叉搜索树
如果树中的每个节点都具有相同的值，则二叉搜索树是单值的。
问题
我们需要编写一个JavaScript函数，该函数接受BST的根并当且仅当给定的树是单值时才返回true，否则返回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