-
Notifications
You must be signed in to change notification settings - Fork 21
Expand file tree
/
Copy pathbinaryTreePaths.java
More file actions
78 lines (69 loc) · 2.2 KB
/
Copy pathbinaryTreePaths.java
File metadata and controls
78 lines (69 loc) · 2.2 KB
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
/*
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
String path = "";
treePaths(root, paths, path);
return paths;
}
private void treePaths(TreeNode root, List<String> paths, String path){
if(root == null){
return;
}
path += root.val + "->";
treePaths(root.left, paths, path);
treePaths(root.right, paths, path);
if(root.left == null && root.right == null){
/* "->" consider as two characters, '-' and '>', that's why -2 */
paths.add(path.substring(0, path.length() -2)); //to get rid of the last "->"
}
}
// second way for the second function
private void findPath(List<String> list, TreeNode root, String path) {
if (root == null) return;
path += root.val;
if (root.left == null && root.right == null) {
list.add(path);
} else {
path += "->"; // dont need to get rid of "->"
findPath(list, root.left, path);
findPath(list, root.right, path);
}
}
}
//using String concatenation copy string each time, using StringBuilder to improve,
//but StringBuilder is mutable, it will hold its value after backtracking, so a lenth needs
//to be set before going into recursion.
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
helper(res, root, sb);
return res;
}
private void helper(List<String> res, TreeNode root, StringBuilder sb) {
if(root == null) {
return;
}
int len = sb.length(); //remember the length before going into recursion
sb.append(root.val);
if(root.left == null && root.right == null) {
res.add(sb.toString());
} else {
sb.append("->");
helper(res, root.left, sb);
helper(res, root.right, sb);
}
sb.setLength(len); //set the lenth back
}