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"]
Answer:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
if(root==null){
return res;
}
List<List<Integer>> tmp = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
Util(root, path, tmp);
for(int i=0;i<tmp.size();++i){
List<Integer> path_int = tmp.get(i);
String path_str = convertStr(path_int);
res.add(path_str);
}
return res;
}
public void Util(TreeNode root, List<Integer> path, List<List<Integer>> res){
if(root==null){
return;
}
//edge case
path.add(root.val);
if(root.left==null && root.right==null){
//clone a new path array
ArrayList<Integer> path_new = new ArrayList<Integer>(path);
res.add(path_new);
//backtrack!
path.remove(path.size()-1);
return;
}
//Recursive case
Util(root.left, path, res);
Util(root.right, path, res);
//backtrack!
path.remove(path.size()-1);
return;
}
public String convertStr(List<Integer> path){
if(path == null || path.size()==0) return null;
StringBuilder sb = new StringBuilder();
int len = path.size();
for(int i=0; i<len-1; ++i){
sb.append(path.get(i));
sb.append("->");
}
sb.append(path.get(len-1));
return sb.toString();
}
}
No comments:
Post a Comment