-
Notifications
You must be signed in to change notification settings - Fork 1
/
112.路径总和.java
55 lines (55 loc) · 1.4 KB
/
112.路径总和.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
* @lc app=leetcode.cn id=112 lang=java
*
* [112] 路径总和
*
* https://leetcode-cn.com/problems/path-sum/description/
*
* algorithms
* Easy (47.35%)
* Likes: 172
* Dislikes: 0
* Total Accepted: 29K
* Total Submissions: 60.8K
* Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'
*
* 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
*
* 说明: 叶子节点是指没有子节点的节点。
*
* 示例:
* 给定如下二叉树,以及目标和 sum = 22,
*
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
*
*
* 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
*
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
sum -= root.val;
if (root.left == null && root.right == null) {//叶子节点
return sum == 0;
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}