// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
// 题目来源：力扣（LeetCode）
// 指定数据结构
// function Tree(val, left, right) {
// this.val = val === undefined ? 0 : val;
// this.left = left === undefined ? null : left;
// this.right = right === undefined ? null : right;
// }
// 第一种解法：递归
// 大问题转化为小问题
var hasPathSum1 = function (root, targetSum) {
if (!root) {
return 0;
}
if (targetSum == root.val && !root.left && !root.right) {
return true;
}
return (
hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val)
);
};
// 第二种解法：深度优先
var hasPathSum2 = function (root, targetSum) {
if (!root) {
return false;
}
let result = false;
function dfs(root, l) {
if (!root) {
return;
}
if (l == targetSum && !root.left && !root.right) {
result = true;
}
if (root.left) {
dfs(root.left, l + root.left.val);
}
if (root.right) {
dfs(root.right, l + root.right.val);
}
}
dfs(root, root.val);
return result;
};
// 第三种解法：广度优先
var hasPathSum3 = function (root, targetSum) {
if (!root) {
return false;
}
const treeArray = [[root, root.val]];
while (treeArray.length) {
const [subTree, sum] = treeArray.shift()
if (sum == targetSum && !subTree.left && !subTree.right) {
return true;
}
if (subTree.left) {
treeArray.push([subTree.left, sum + subTree.left.val]);
}
if (subTree.right) {
treeArray.push([subTree.right, sum + subTree.right.val]);
}
}
return false;
};
2023-03-19 力扣112 基础路径总和
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目描述（简单难度） 给定一个sum，判断是否有一条从根节点到叶子节点的路径，该路径上所有数字的和等于sum。 解...
- 题目描述（中等难度） 112 题 的升级版，给定一个sum，输出从根节点开始到叶子节点，和为sum 的所有路径可能...
- 路径总和 题目链接 思路：递归 使用递归遍历整棵树 代码如下： 时间复杂度：遍历了二叉树的每个节点，时间复杂度为O...
- 112. 路径总和[https://leetcode-cn.com/problems/path-sum/] 问题描...
