【算法】遍历根到所有叶子节点的路径

发表于 阅读次数：

遍历根到所有叶子节点的路径

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package com.lyloou.tool.tree;

import java.util.ArrayList;
import java.util.List;


/*
 *
 * **** 示例1 ****
         1
    2          3
  4   5      6   7

 输出如下：
 1 2 4
 1 2 5
 1 3 6
 1 3 7


 * **** 示例2 ****
       1
  2        3
     5
  a = TreeNode(1)
  b = TreeNode(2)
  c = TreeNode(3)
  d = TreeNode(5)
  a.left = b
  a.right =  c
  b.right = d

 输出如下：
 ['1->2->5', '1->3']
 */
public class Solution2 {
    public static void main(String[] args) {
        test1();
        test2();
    }

    private static void test1() {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(5);
        a.left = b;
        a.right = c;
        b.right = d;
        System.out.println(binaryTreePaths(a));
    }

    private static void test2() {
        TreeNode a1 = new TreeNode(1);
        TreeNode a2 = new TreeNode(2);
        TreeNode a3 = new TreeNode(3);
        TreeNode a4 = new TreeNode(4);
        TreeNode a5 = new TreeNode(5);
        TreeNode a6 = new TreeNode(6);
        TreeNode a7 = new TreeNode(7);
        a1.left = a2;
        a1.right = a3;
        a2.left = a4;
        a2.right = a5;
        a3.left = a6;
        a3.right = a7;
        System.out.println(binaryTreePaths(a1));
    }

    /**
     * @param root the root of the binary tree
     * @return all root-to-leaf paths
     */
    private static List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        // 有几个叶子节点，就有几条路径
        if (isLeaf(root)) {
            List<String> list = new ArrayList<>();
            list.add(root.val + "");
            return list;
        }

        // 获取左子树的列表，循环向元素前面追加当前值
        final List<String> leftList = binaryTreePaths(root.left);
        for (int i = 0; i < leftList.size(); i++) {
            leftList.set(i, root.val + "->" + leftList.get(i));
        }

        // 获取右子树的列表，循环向元素前面追加当前值
        final List<String> rightList = binaryTreePaths(root.right);
        for (int i = 0; i < rightList.size(); i++) {
            rightList.set(i, root.val + "->" + rightList.get(i));
        }

        // 拼接成一个列表返回
        List<String> result = new ArrayList<>(leftList.size() + rightList.size());
        result.addAll(leftList);
        result.addAll(rightList);
        return result;
    }


    /**
     * 判断node是否为叶子节点
     *
     * @param node 节点
     * @return true 为叶子节点，
     */
    private static boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }
}

运行结果

all-to-leaf-path-2021-05-25-00-35-39