在 JavaScript 中查找 BST 的左叶总和
问题
我们需要编写一个JavaScript函数，它将二叉搜索树的根作为唯一参数。
该函数应该简单地计算存储在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(){
//二叉搜索树的根
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
热门推荐
1 泰迪狗狗如何训练
3 狗狗训练图
5 狗狗训练方法
6 训练狗狗不咬人
8 敏捷训练狗狗
10 训练狗狗吃饭
11 泰迪狗狗训练
12 狗狗从多大开始训练
13 狗狗训练学校费用
14 怎么去训练狗狗
15 狗狗训练狗狗
16 狗狗训练教程
17 训练狗狗装死
18 泰迪狗狗的训练方法