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"]
Solution：DFS
Time Complexity: O(N) Space Complexity: O(N) 递归缓存
Solution Code：
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
dfs(root, "", result);
return result;
}
private void dfs(TreeNode node, String cur_res, List<String> result) {
if(node == null) return;
if(node.left == null && node.right == null) {
result.add(cur_res + String.valueOf(node.val));
return;
}
cur_res += String.valueOf(node.val) + "->";
dfs(node.left, cur_res, result);
dfs(node.right, cur_res, result);
}
}
