FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaArithmetic/src/LeetCode/LeetCode437.java at master · Edwardlinge/JavaArithmetic · GitHub
Edwardlinge
JavaArithmetic
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
LeetCode437.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
92 lines (70 loc) · 2.37 KB
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
LeetCode437.java
Copy path
File metadata and controls
92 lines (70 loc) · 2.37 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package
LeetCode
;
public
class
LeetCode437
{
/// 437. Path Sum III
/// https://leetcode.com/problems/path-sum-iii/description/
/// 时间复杂度: O(n), n为树的节点个数
/// 空间复杂度: O(h), h为树的高度
/// Definition for a binary tree node.
public
static
class
TreeNode
{
int
val
;
TreeNode
left
;
TreeNode
right
;
TreeNode
(
int
x
) {
val
=
x
;
}
}
// 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
public
int
pathSum
(
TreeNode
root
,
int
sum
) {
if
(
root
==
null
)
return
0
;
return
findPath
(
root
,
sum
)
+
pathSum
(
root
.
left
,
sum
)
+
pathSum
(
root
.
right
,
sum
);
}
// 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
// 返回这样的路径个数
private
int
findPath
(
TreeNode
node
,
int
num
) {
if
(
node
==
null
)
return
0
;
int
res
=
0
;
// 找到node.val == num 说明就已经找到一条路径了。
if
(
node
.
val
==
num
)
res
+=
1
;
res
+=
findPath
(
node
.
left
,
num
-
node
.
val
);
res
+=
findPath
(
node
.
right
,
num
-
node
.
val
);
return
res
;
}
public
static
void
main
(
String
[]
args
) {
// 手动创建Leetcode题页上的测试用例。
// 当然, 有更好的更智能的创建二叉树的方式, 有兴趣的同学可以自行研究编写程序:)
/*****************
* 测试用例:
*
* 10
* / \
* 5 -3
* / \ \
* 3 2 11
* / \ \
* 3 -2 1
*****************/
TreeNode
node1
=
new
TreeNode
(
3
);
TreeNode
node2
=
new
TreeNode
(-
2
);
TreeNode
node3
=
new
TreeNode
(
3
);
node3
.
left
=
node1
;
node3
.
right
=
node2
;
TreeNode
node4
=
new
TreeNode
(
1
);
TreeNode
node5
=
new
TreeNode
(
2
);
node5
.
right
=
node4
;
TreeNode
node6
=
new
TreeNode
(
5
);
node6
.
left
=
node3
;
node6
.
right
=
node5
;
TreeNode
node7
=
new
TreeNode
(
11
);
TreeNode
node8
=
new
TreeNode
(-
3
);
node8
.
right
=
node7
;
TreeNode
node9
=
new
TreeNode
(
10
);
node9
.
left
=
node6
;
node9
.
right
=
node8
;
System
.
out
.
println
((
new
LeetCode437
()).
pathSum
(
node9
,
8
));
}
}
Back
|
FazBrowse Home
|
New Git URL