Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
DFS
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList();
if(root == null) return res;
Helper(res, String.valueOf(root.val), root);
return res;
}
public void Helper(List<String> res, String comb, TreeNode root) {
if(root.left == null && root.right == null){
res.add(comb);
}else{
if(root.left != null){
Helper(res, comb + "->" + root.left.val, root.left);
}
if(root.right != null){
Helper(res, comb + "->" + root.right.val, root.right);
}
}
}
BFS
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList();
if(root == null) return res;
Queue<TreeNode> que = new LinkedList();
Queue<String> path = new LinkedList();
que.add(root);
path.add(String.valueOf(root.val));
while(!que.isEmpty()){
TreeNode n = que.poll();
String currPath = path.poll();
if(n.left == null && n.right == null){
res.add(currPath);
}
if(n.left != null){
que.add(n.left);
path.add(currPath + "->" + n.left.val);
}
if(n.right != null){
que.add(n.right);
path.add(currPath + "->" + n.right.val);
}
}
return res;
}