ปัญหา
เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับรูทของ Binary Search Tree เป็นอาร์กิวเมนต์เดียว
ฟังก์ชันควรคำนวณผลรวมของข้อมูลที่เก็บไว้ในด้านซ้ายของ BST
ตัวอย่างเช่น หากต้นไม้มีลักษณะเช่นนี้ −
8 / \ 1 10 / \ 5 17
จากนั้นผลลัพธ์ควรเป็น −
const output = 6;
คำอธิบายผลลัพธ์:
เพราะมีเหลืออยู่สองใบในต้นไม้ที่มีค่า 1 และ 5
ตัวอย่าง
รหัสสำหรับสิ่งนี้จะเป็น −
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)); ผลลัพธ์
ผลลัพธ์ในคอนโซลจะเป็น -
7
