力扣257-二叉树的所有路径

发表于 分类于 阅读次数： 本文字数： 373 阅读时长 ≈ 1 分钟

题目描述

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

1
2
输入：root = [1]
输出：["1"]

提示：

  • 树中节点的数目在范围 [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;
    }
//    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);
//    }
}