257二叉树的所有路径
程序员文章站
2022-05-20 19:25:05
...
题目描述
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输出: [“1->2->5”, “1->3”]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
思路分析
递归终止的条件是什么?一次递归中要进行什么操作?递归想要返回什么信息?
基于前序递归模板。
终止条件:节点为空
递归中操作:为叶节点时,将路径加入list,不为叶节点就把此节点的值入str
提交初版代码后发现执行用时13ms…所以将String换成StringBuffer,SB需要进行回溯处理。
代码实现
/**
* 直接用string做传递
* @param root
* @return
*/
public static List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
process2(root, list, "");
return list;
}
public static void process2(TreeNode root, List<String> list, String str) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
str = str + "" + root.val;
list.add(str);
} else {
str = str + root.val + "->";
}
process2(root.left, list, str);
process2(root.right, list, str);
}
/**
* stringbuffer做传递
* @param root
* @return
*/
public static List<String> binaryTreePaths1(TreeNode root) {
List<String> list = new ArrayList<>();
process1(root, list, new StringBuffer());
return list;
}
public static void process1(TreeNode root, List<String> list, StringBuffer str) {
if (root == null) {
return;
}
str.append(root.val);
if (root.left == null && root.right == null) {
list.add(str.toString());
} else {
if (root.left != null) {
str.append("->");
process1(root.left, list, str);
str.delete(str.lastIndexOf("->"), str.length());
}
if (root.right != null) {
str.append("->");
process1(root.right, list, str);
str.delete(str.lastIndexOf("->"), str.length());
}
}
}
下一篇: 404左叶子之和
推荐阅读