LeetCode 112. 路径总和(Path Sum) 10
2024-09-26 08:49:48
112. 路径总和
112. Path Sum
题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
每日一算法2019/5/13Day 10LeetCode112. Path Sum
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true，因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
Java 实现
Recursive Solution
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int target) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == target) {
return true;
}
return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);
}
}
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int target) {
List<Integer> answer = new ArrayList<>();
if (root == null) {
return false;
}
searchPath(root, 0, target, answer);
if (answer.contains(target)) {
return true;
}
return false;
}
private void searchPath(TreeNode root, int sum, int target, List<Integer> answer) {
if (root.left == null && root.right == null) {
answer.add(sum + root.val);
}
if (root.left != null) {
searchPath(root.left, sum + root.val, target, answer);
}
if (root.right != null) {
searchPath(root.right, sum + root.val, target, answer);
}
}
}
相似题目
参考资料
最新文章
- editplus工具支持sql高亮提示
- CentOS 7 安装php开发环境
- C# 文件下载四方法
- 前端利器：SASS基础与Compass入门
- 【转】Visual Studio 非常实用的调试技巧
- git曲线
- 游戏控制杆OUYA游戏开发快速入门教程
- explicit关键字
- linux中fork（）函数详解
- linux shell 命令学习(5) xxd- make a hexdump or do the reverse.
- ZOJ 2750 Idiomatic Phrases Game（Dijkstra）
- java 动态代理的实现
- redis存取对象
- 如何在Mac上安全彻底的卸载软件？
- js学习——基础知识
- Python——多进程
- 2018-2019-1 20189206 《Linux内核原理与分析》第七周作业
- JavaScript之图片操作6
- 来自Unix/Linux的编程启发录
- mysql 权限管理 针对表的字段 级别 授权 columns_priv表