Binary Tree Paths
题目:
Given a binary tree, return all root-to-leaf paths.
分析:
15分钟,无bug,注意
res.add( convertToString(path) );
// res.add( new String ( convertToString(path) ) );
// 两个都可以,就是说函数返回值本身就放在一个新的instance里面
解法:
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public String convertToString(List<TreeNode> path) {
String res = "";
for (int i = 0; i < path.size() - 1; i++) {
res = res + Integer.toString(path.get(i).val) + "->";
}
int last = path.get(path.size() - 1).val;
res += Integer.toString(last);
return res;
}
public void dfs(List<String> res, List<TreeNode> path, TreeNode root) {
if (root.left == null && root.right == null) {
res.add( convertToString(path) );
// res.add( new String ( convertToString(path) ) );
// 两个都可以,就是说函数返回值本身就放在一个新的instance里面
return;
}
if (root.left != null) {
path.add(root.left);
dfs(res, path, root.left);
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right);
dfs(res, path, root.right);
path.remove(path.size() - 1);
}
}
public List<String> binaryTreePaths(TreeNode root) {
// Write your code here
List<String> res = new ArrayList<String>();
if (root == null) {
return res;
}
List<TreeNode> path = new ArrayList<TreeNode>();
path.add(root);
dfs(res, path, root);
return res;
}
}