[题目链接]

preview -> 题目难度:简单
给一个二叉树,以及一个target值,找到所有符合根节点到叶子节点的路径和为target的路径

题解

需要使用回溯, 先从root出发, 然后更新target值, 然后向左子树找, 然后向右子树找, 这个过程是递归进行的, 然后如果没有符合的, 就回溯, 删除上一个节点的信息, 这里的终止条件是已经到达根节点, 并且target值已经为0, 这个时候就找到了一条路径

源码

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
class Solution {
    LinkedList<Integer> path = new LinkedList<>();

    LinkedList<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        recur(root, target);

        return res;
    }

    public void recur (TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;

        if (target == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path)); // 复制一手
        }
        recur(root.left, target);
        recur(root.right, target);

        path.removeLast();

    }
}