深度优先遍历 DFS
解题思路
先进行 dfs 深度优先遍历，再判断左节点是不是叶子节点；
把所有的叶子节点的值相加；
复杂度
-
时间复杂度：
O(n)，其中 n 是树中的节点个数； -
空间复杂度：
O(n)；
代码实现
var sumOfLeftLeaves = function (root) {
const travese = (root) => {
if (root === null) return 0;
// left 是单独的节点
if (root.left && root.left.left === null && root.left.right === null) {
sum += root.left.val;
}
travese(root.left);
travese(root.right);
}
let sum = 0;
travese(root);
return sum;
};
广度优先遍历 BFS
解题思路
先进行层序遍历，再判断每一层的左节点是不是叶子节点；
把所有的叶子节点的值相加；
复杂度
-
时间复杂度：
O(n)，其中 n 是树中的节点个数； -
空间复杂度：
O(n)；
实现代码
var sumOfLeftLeaves = function (root) {
if (root === null) return 0;
let sum = 0;
const queue = [root]; // 声明队列用于存储后续数据
// 遍历队列
while (queue.length) {
let curLevel = []; // 针对本轮操作，创建一个数组
let len = queue.length; // 一层的数据量
while (len--) {
// 将本次操作的结点出队
const node = queue.shift();
curLevel.push(node.val);
if (node.left && node.left.left === null && node.left.right === null) {
sum += node.left.val;
}
// 检测是否存在左右子结点，如果有，入队即可
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return sum;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 257. 二叉树的所有路径
上一篇
评论
