Vấn đề
Chúng tôi được yêu cầu viết một hàm JavaScript lấy gốc của Cây tìm kiếm nhị phân làm đối số duy nhất.
Hàm sẽ chỉ đơn giản là tính toán tổng dữ liệu được lưu trữ trong các phần bên trái của BST.
Ví dụ:nếu Cây trông như thế này -
8 / \ 1 10 / \ 5 17
Sau đó, đầu ra phải là -
const output = 6;
Giải thích đầu ra:
Vì có hai lá bên trái trong Cây có giá trị 1 và 5.
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(3);
BST.insert(6);
BST.insert(6);
BST.insert(9);
BST.insert(4);
BST.insert(7);
const isLeaf = node => {
if (!node) return false;
return (node.left === null && node.right === null);
}
const traverseTreeAndSumLeftLeaves = (root, sum = 0) => {
if (!root) return sum;
if (isLeaf(root)) return sum;
if (root.left) {
if (isLeaf(root.left)) {
sum += root.left.data;
traverseTreeAndSumLeftLeaves(root.left, sum);
} else sum = traverseTreeAndSumLeftLeaves(root.left, sum);
}
if (root.right) {
if (isLeaf(root.right)) return sum;
else {
sum = traverseTreeAndSumLeftLeaves(root.right, sum);
}
}
return sum;
};
console.log(traverseTreeAndSumLeftLeaves(BST.root)); Đầu ra
Đầu ra trong bảng điều khiển sẽ là -
7