跳到主内容

【算法题】路径总和 - 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);
};

原题地址:https://leetcode-cn.com/problems/path-sum