257. 二叉树的所有路径
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入: root = [1,2,3,null,5]
输出:[“1->2->5”,“1->3”]
示例 2:
输入: root = [1]
输出:[“1”]
提示:
- 树中节点的数目在范围
[1, 100]
内 - − 100 ≤ N o d e . v a l ≤ 100 -100 \leq Node.val \leq 100 −100≤Node.val≤100
解法一(前序遍历递归+dfs)
思路分析:
-
因为要求从根节点到叶子节点的路径,所以遍历二叉树从根节点开始,即采用前序遍历中左右
-
使用递归来实现前序遍历更为方便
-
然后考虑递归的边界条件,当遍历的节点为空时,结束继续往下遍历,当遍历到叶子节点时,则保存该条遍历路径,并结束遍历
-
考虑递归的过程,即在遍历到叶子节点时,保存遍历路径,若不是叶子节点,则继续往深处遍历
实现代码如下:
java">class Solution {
List<String> ans = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs("", root);
return ans;
}
private void dfs(String result, TreeNode node) {
if (node == null)
return ;
result += node.val; // 路径增加
if (node.left == null && node.right == null) {
// 遍历到叶子节点 保存路径
ans.add(result);
return ;
}
dfs(result+"->", node.left); // 向左往深处遍历
dfs(result+"->", node.right); // 向右往深处遍历
}
}
提交结果如下:
解答成功:
执行耗时:8 ms,击败了32.93% 的Java用户
内存消耗:41.8 MB,击败了5.10% 的Java用户
复杂度分析:
优化解法一(StringBuffer)
思路分析:
-
使用StringBuffer来代替字符串,可变字符串追加或删除元素为 O ( 1 ) O(1) O(1),能够有更好的性能
-
保存到叶子节点的路径后,应该回溯删除该叶子节点值,往深处遍历左右子树结束时,也应该删除该节点,回归初始,便于往别的分支继续递归
实现代码如下:
java">class Solution {
List<String> ans = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(new StringBuffer(), root);
return ans;
}
private void dfs(StringBuffer result, TreeNode node) {
if (node == null)
return ;
int size = result.length(); // 记录进入函数时的长度 便于递归回溯
result.append(node.val); // 路径增加
if (node.left == null && node.right == null) {
// 遍历到叶子节点 保存路径
ans.add(result.toString());
result.delete(size, result.length()); // 回溯
return ;
}
result.append("->");
dfs(result, node.left); // 向左往深处遍历
dfs(result, node.right); // 向右往深处遍历
result.delete(size, result.length()); // 回溯
}
}
提交结果如下:
解答成功:
执行耗时:1 ms,击败了99.97% 的Java用户
内存消耗:41.1 MB,击败了26.21% 的Java用户
复杂度分析:
-
时间复杂度:只有当保存根节点到叶子节点的路径时,需要将结果转化为
String
,需要花费 O ( n ) O(n) O(n) -
空间复杂度: O ( n 2 ) O(n^2) O(n2),递归对空间的消耗,以及递归过程中需要对字符串路径的存储