257 Binary Tree Paths

257. Binary Tree Paths

1. Question

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
1
2
/ \
3
2 3
4
\
5
5
Copied!
All root-to-leaf paths are:
1
["1->2->5", "1->3"]
Copied!

2. Implementation

(1) DFS
1
class Solution {
2
public List<String> binaryTreePaths(TreeNode root) {
3
List<String> res = new ArrayList<>();
4
getTreePaths(root, "", res);
5
return res;
6
}
7
8
public void getTreePaths(TreeNode node, String curPath, List<String> res) {
9
if (node == null) {
10
return;
11
}
12
13
if (node.left == null && node.right == null) {
14
res.add(curPath + node.val);
15
return;
16
}
17
18
getTreePaths(node.left, curPath + node.val + "->", res);
19
getTreePaths(node.right, curPath + node.val + "->", res);
20
}
21
}
Copied!
(2) BFS
1
class Solution {
2
public List<String> binaryTreePaths(TreeNode root) {
3
List<String> res = new ArrayList<>();
4
if (root == null) {
5
return res;
6
}
7
8
Queue<TreeNode> queue = new LinkedList<>();
9
Queue<String> path = new LinkedList<>();
10
11
queue.add(root);
12
path.add("");
13
14
while (!queue.isEmpty()) {
15
int size = queue.size();
16
17
for (int i = 0; i < size; i++) {
18
TreeNode curNode = queue.remove();
19
String curPath = path.remove();
20
21
if (curNode.left == null && curNode.right == null) {
22
res.add(curPath + curNode.val);
23
}
24
25
if (curNode.left != null) {
26
queue.add(curNode.left);
27
path.add(curPath + curNode.val + "->");
28
}
29
30
if (curNode.right != null) {
31
queue.add(curNode.right);
32
path.add(curPath + curNode.val + "->");
33
}
34
}
35
}
36
return res;
37
}
38
}
Copied!

3. Time & Space Complexity

(1) DFS: 时间复杂度: O(n), 空间复杂度: O(h)
(2) BFS: 时间复杂度: O(n), 空间复杂度: O(w)