
题目描述
257. 二叉树的所有路径
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:

1 2
| 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"]
|
示例 2:
提示:
- 树中节点的数目在范围
[1, 100]
内
-100 <= Node.val <= 100
解题思路
回溯算法求解

代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| public class Solution257Case2 { public static List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<>(); constructPaths(root, "", paths); return paths; }
public static void constructPaths(TreeNode root, String path, List<String> paths) { if (root != null) { StringBuffer pathSB = new StringBuffer(path); pathSB.append(root.val); if (root.left == null && root.right == null) { paths.add(pathSB.toString()); } else { pathSB.append("->"); constructPaths(root.left, pathSB.toString(), paths); constructPaths(root.right, pathSB.toString(), paths); } } }
public static void main(String[] args) { TreeNode node5 = new TreeNode(5); TreeNode node3 = new TreeNode(3); TreeNode node2 = new TreeNode(2, null, node5); TreeNode node1 = new TreeNode(1, node2, node3); binaryTreePaths(node1); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| public class Solution257Case1 { public final List<List<String>> res = new ArrayList<>(); public final List<String> path = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) { preOrder(root); ArrayList<String> list = new ArrayList<>(); res.forEach(item -> { String str = str(item); list.add(str); }); return list; }
public void preOrder(TreeNode root) { if (null == root) { return; } path.add(root.val + ""); if (null == root.left && null == root.right) { res.add(new ArrayList<>(path)); } preOrder(root.left); preOrder(root.right); path.remove(path.size() - 1); }
public String str(List<String> path) { StringBuilder sb = new StringBuilder(); for (String s : path) { sb.append(s).append("->"); } if (sb.length() > 2) { return sb.substring(0, sb.length() - 2); } return null; }
}
|