-
Notifications
You must be signed in to change notification settings - Fork 8
/
SumRootToLeafNumbers.java
79 lines (67 loc) · 1.79 KB
/
SumRootToLeafNumbers.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package depthfirstsearch;
// Source : https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Id : 129
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2020/8/17
// Topic : Depth-First Search
// Level : Medium
// Other :
// Tips :
// Links : 257
// Result : 100.00% 87.92%
import java.util.LinkedList;
import java.util.List;
public class SumRootToLeafNumbers {
List<String> list = new LinkedList<>();
// 6.22% 14ms 5.06%
public int sumNumbers(TreeNode root) {
if (root == null)
return 0;
dfs("", root);
int sum = 0;
for (String s : list) {
System.out.println(s);
sum += Integer.valueOf(s);
}
return sum;
}
public void dfs(String prefix, TreeNode node) {
prefix += node.val;
if (node.left == null && node.right == null) {
list.add(prefix);
return;
}
if (node.left == null)
dfs(prefix, node.right);
else if (node.right == null)
dfs(prefix, node.left);
else {
dfs(prefix, node.right);
dfs(prefix, node.left);
}
}
int sum = 0;
public int sumNumbers1(TreeNode root) {
// public int sumNumbers(TreeNode root) {
dfs(root, 0);
return sum;
}
public void dfs(TreeNode root, int curSum) {
if (root == null)
return;
if (root.left == null && root.right == null) {
sum += curSum * 10 + root.val;
return;
}
dfs(root.left, curSum * 10 + root.val);
dfs(root.right, curSum * 10 + root.val);
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}