[LeetCode] LC257 - Binary Tree Paths

Description

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input:

1
/ \
2 3
\
5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

> Solve problem here

Thoughts

DFS recursive (top-down)

The most straight forward way to solve this problen is via recursive DFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dfs traverse top down
public List<String> binaryTreePaths0(TreeNode root) {
// write your code here
List<String> res = new ArrayList<>();
helper(root, res, "");
return res;
}

public void helper(TreeNode node, List<String> res, String s) {
if (node == null) return;
if (node.left == null && node.right == null) {
res.add(new String(s + node.val));
return;
}

// prep new string
String newStr = new String(s + node.val + "->");

// left & right
helper(node.left, res, newStr);
helper(node.right, res, newStr);
}

Add all nodes’s value along the way (top-down) and add path string into List<String> solution at leaf node.

DFS recursive (bottom-up)

The bottom up recursive approach is bit harder to come up with. I was not able to come up with it at first place.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ref: https://leetcode.com/problems/binary-tree-paths/discuss/68282/Clean-Java-solution-(Accepted)-without-any-helper-recursive-function

public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new LinkedList<>(); // new List wo/ worry prev list, smart
if(root == null) return paths;
if(root.left == null && root.right == null){
paths.add(root.val+"");
return paths;
}
for (String path : binaryTreePaths(root.left)) {
paths.add(root.val + "->" + path);
}
for (String path : binaryTreePaths(root.right)) {
paths.add(root.val + "->" + path);
}

return paths;
}

DFS iterative (top-bottom)

DFS iterative approach can pre-order traversal, which is a top-down approach. The bottom-up appraoch is simliar w/ in-order traversal (bottom-up) but not implemented, below is the DFS iterative top-down via pre-order traversal.

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
// dfs iterative + preorder (top-down)
public List<String> binaryTreePaths0(TreeNode root) {
List<String> res = new ArrayList<>();

if (root == null) return res;
Deque<TreeNode> stack = new ArrayDeque<>();
Deque<String> paths = new ArrayDeque<>();
stack.push(root);
paths.push(""); // key

while (!stack.isEmpty()) {
TreeNode node = stack.pop();
String path = paths.pop();
if (node.left == null && node.right == null) {
res.add(path + node.val);
}
if (node.right != null) {
stack.push(node.right);
paths.push(path + node.val + "->");
}
if (node.left != null) {
stack.push(node.left);
paths.push(path + node.val + "->");
}
}

return res;
}

BFS iterative

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
// bfs iterative + leverl order
public List<String> binaryTreePaths0(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;

Deque<TreeNode> queue = new ArrayDeque<>();
Deque<String> paths = new ArrayDeque<>();
queue.offer(root);
paths.offer(""); // key

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
String path = paths.poll();
if (node.left == null && node.right == null) {
res.add(path + node.val);
}

if (node.left != null) {
queue.offer(node.left);
paths.offer(path + node.val + "->");
}

if (node.right != null) {
queue.offer(node.right);
paths.offer(path + node.val + "->");
}
}

return res;
}

Summary

  • DFS recursive (bottom-up)
  • DFS recursive (top-down)
  • DFS iterative (top-down, pre-order traversal)
  • DFS iterative (bottom-up, in-order traversal)
  • BFS iterative
  • BFS iterative is similiar to DFS iterative (top-down, preorder)

Logs

  • 02/04/19: solution added
  • TODO: dfs recursive/iterative bottom-up

Reference