【算法题】路径总和 - Javascript版本
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
,否则,返回 false
。
叶子节点 是指没有子节点的节点。
示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:

输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
使用 BFS 迭代
维护一个队列记录当前节点,并根据当前节点搜索下一层
维护一个队列记录路径和 temp,并时刻更新(将下一层的节点值计算进去,并时刻判断是否为叶子节点,如果是叶子节点则将 temp 与targetSum
进行比较)
跟 层序遍历 的代码很像
var hasPathSum = function (root, targetSum) {
if (!root) {
return false;
}
// BFS法 创建两个数组 一个记录所有节点 一个记录路径和
const queue = [];
const res = [];
queue.push(root);
res.push(root.val);
// 进入BFS
while (queue.length) {
const top = queue.pop();
const temp = res.pop();
// 如果遍历到叶子节点处时 路径和=targetSum 则返回true
if (top.left === null && top.right === null) {
if (temp === targetSum) return true;
}
// 如层序遍历一般更新queue与路径和数组
if (top.left) {
queue.push(top.left);
res.push(temp + top.left.val);
}
if (top.right) {
queue.push(top.right);
res.push(temp + top.right.val);
}
}
return false;
};
使用递归,DFS
与广度优先使用计算路径和的思路反了过来
深搜使用的思想是,每层计算都进行 targetSum - root.val
如果到叶子节点时 targetSum === root.val
说明路径和符合要求了
var hasPathSum = function (root, targetSum) {
if (root === null) {
return false;
}
// 搜到叶子节点,则判断当前节点值是否等于目标值
if (root.left === null && root.right === null) {
return root.val === targetSum;
}
// 还没搜到叶子节点,则进行 目标值-当前节点值,并继续往下搜
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};