题目描述

链接: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

给定二叉树的根节点root和一个整数目标targetSum, 找出所有从根节点到叶子节点路径总和等于给定目标和的路径

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

示例1:

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2], [5,8,4,5]]

有两条路径加起来之和等于22

示例2:

img

输入：root = [1,2,3], targetSum = 5
输出：[]

没有符合条件的路径

解题思路

DFS

每次遍历时, 将当前节点加入到路径中, 并将总和减去当前节点的值

判断当前节点是否是叶子节点, 如果是则判断和是否已经等于0, 如果等于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
	List<List<Integer>> res = new LinkedList<>();
	LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int target) {
    		dfs(root, target);
		    return res;
	}

	private void dfs(TreeNode node, int target) {
		    if (node == null) {
        			return;
    		}
		    // 保存当前路径
    		path.addLast(node.val);
		    // 将目标值减去当前节点的值
    		target -= node.val;
		    // 如果是叶子节点，并且目标值为0也就是满足条件后，将当前路径放到结果集合中
    		if (node.left == null && node.right == null && target == 0) {
			        res.add(new LinkedList<>(path));
		    }
    		// 遍历左节点
    		dfs(node.left, target);
		    // 遍历右节点
    		dfs(node.right, target);
    		// 将当前节点的值从路径中移除
		    path.removeLast();
	}