Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita4faad7

Browse files
committed
feat: add 112
1 parent6c71c2a commita4faad7

File tree

5 files changed

+144
-41
lines changed

5 files changed

+144
-41
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@
3535
|108|[Convert Sorted Array to Binary Search Tree][108]|Tree, Depth-first Search|
3636
|110|[Balanced Binary Tree][110]|Tree, Depth-first Search|
3737
|111|[Minimum Depth of Binary Tree][111]|Tree, Depth-first Search, Breadth-first Search|
38+
|112|[Path Sum][112]|Tree, Depth-first Search|
3839

3940

4041
##Medium
@@ -85,6 +86,7 @@
8586
[108]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/108/README.md
8687
[110]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/110/README.md
8788
[111]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/111/README.md
89+
[112]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/112/README.md
8890

8991
[008]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
9092
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md

‎note/112/README.md‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
#[Path Sum][title]
2+
3+
##Description
4+
5+
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
6+
7+
For example:
8+
9+
Given the below binary tree and`sum = 22`,
10+
11+
```
12+
5
13+
/ \
14+
4 8
15+
/ / \
16+
11 13 4
17+
/ \ \
18+
7 2 1
19+
20+
```
21+
22+
return true, as there exist a root-to-leaf path`5->4->11->2` which sum is 22.
23+
24+
**Tags:** Tree, Depth-first Search
25+
26+
27+
##思路
28+
29+
题意是查找二叉树中是否存在从根结点到叶子的路径和为某一值，利用深搜在遇到叶子节点时判断是否满足即可。
30+
31+
32+
```java
33+
/**
34+
* Definition for a binary tree node.
35+
* public class TreeNode {
36+
* int val;
37+
* TreeNode left;
38+
* TreeNode right;
39+
* TreeNode(int x) { val = x; }
40+
* }
41+
*/
42+
classSolution {
43+
publicbooleanhasPathSum(TreeNoderoot,intsum) {
44+
if (root==null)returnfalse;
45+
if (root.left==null&& root.right==null)return sum== root.val;
46+
return hasPathSum(root.left, sum- root.val)|| hasPathSum(root.right, sum- root.val);
47+
}
48+
}
49+
```
50+
51+
52+
##结语
53+
54+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
55+
56+
57+
58+
[title]:https://leetcode.com/problems/path-sum
59+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎project/leetcode/.idea/workspace.xml‎

Lines changed: 56 additions & 41 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.
Binary file not shown.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packagecom.blankj.easy._112;
2+
3+
4+
importcom.blankj.structure.TreeNode;
5+
6+
/**
7+
* <pre>
8+
* author: Blankj
9+
* blog : http://blankj.com
10+
* time : 2017/10/09
11+
* desc :
12+
* </pre>
13+
*/
14+
publicclassSolution {
15+
publicbooleanhasPathSum(TreeNoderoot,intsum) {
16+
if (root ==null)returnfalse;
17+
if (root.left ==null &&root.right ==null)returnsum ==root.val;
18+
returnhasPathSum(root.left,sum -root.val) ||hasPathSum(root.right,sum -root.val);
19+
}
20+
21+
publicstaticvoidmain(String[]args) {
22+
Solutionsolution =newSolution();
23+
TreeNodetestData =TreeNode.createTestData("[5,4,8,11,null,13,4,7,2,null,null,null,1]");
24+
TreeNode.print(testData);
25+
System.out.println(solution.hasPathSum(testData,22));
26+
}
27+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp