剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dc8rr/

递归

化加法为减法，如果 target 与路径上的所有值相关之后为 0，说明路径符合要求

public class Solution {
    // 存储结果
    private List<List<Integer>> res = new LinkedList<>();
    // 临时存放路径
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 深度优先搜索路径
        recursion(root, sum);
        return this.res;
    }
    public void recursion(TreeNode node, int target) {
        // 如果为空，说明路径不符合要求。直接返回
        if (node == null) return;
        // 将节点值加入路径中
        path.add(node.val);
        // 减去节点的值
        target -= node.val;
        // 如果是叶子节点 && target 为 0 说明路径符合
        if (node.left == null && node.right == null && target == 0) {
            // 将路径拷贝一份放入结果集
            res.add(new LinkedList<>(path));
        }
        // 分别递归搜索左子树和右子树
        recursion(node.left, target);
        recursion(node.right, target);
        // 回溯时要删除路径的最后一个值
        path.removeLast();
    }
}