1. question: 二叉树的所有路径(简单)
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-paths
示例 1:
1 2
| 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"]
|
示例 2:
提示:
1 2
| 树中节点的数目在范围 [1, 100] 内 -100 <= Node.val <= 100
|
2. answers
这道题可以先用递归的方法做一遍。根节点形成的树的所有路径为根节点分别和以左右孩子节点形成的树的所有路径相拼接。而左右孩子节点的所有路径则又可以递归,以此类推。
代码如下所示:
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 46 47 48 49 50 51 52 53 54
| public class Solution_0026 {
public static List<String> binaryTreePaths(TreeNode root) {
if(root == null) { return null; }
List<String> result = new ArrayList<>();
List<String> leftResult = binaryTreePaths(root.left); List<String> rightResult = binaryTreePaths(root.right);
if(leftResult != null) {
for(String str: leftResult) { result.add(root.val + "->" + str); } }
if(rightResult != null) {
for(String str: rightResult) { result.add(root.val + "->" + str); } }
if(leftResult == null && rightResult == null) { result.add(root.val + ""); }
return result; }
public static void main(String[] args) {
TreeNode tn1 = new TreeNode(5); TreeNode tn2 = new TreeNode(2, null, tn1); TreeNode tn3 = new TreeNode(3); TreeNode tn4 = new TreeNode(1, tn2, tn3);
List<String> strings = binaryTreePaths(tn4); for(String str: strings) { System.out.println(str); } } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。