LeetCode题练习与总结：路径总和Ⅱ--113

一、题目描述

给你二叉树的根节点 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]]

示例 2：

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

示例 3：

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

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

二、解题思路

这个问题可以通过递归的方式解决。我们定义一个递归函数，该函数接受当前节点和当前路径和作为参数。递归函数的工作流程如下：

1. 如果当前节点是空，返回一个空列表。

2. 如果当前节点是叶子节点（即没有子节点），检查当前路径和是否等于目标值。如果是，将当前路径和加入到结果列表中。

3. 如果当前节点不是叶子节点，递归地调用函数：

调用函数，参数是当前节点的左子节点和当前路径和加上当前节点的值。
调用函数，参数是当前节点的右子节点和当前路径和加上当前节点的值。

4. 将两个递归调用中的结果合并到一起，并返回。

三、具体代码

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        pathSum(root, targetSum, new ArrayList<>(), result);
        return result;
    }

    private void pathSum(TreeNode node, int target, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        currentPath.add(node.val);
        if (node.left == null && node.right == null && target == node.val) {
            result.add(new ArrayList<>(currentPath));
        }
        pathSum(node.left, target - node.val, currentPath, result);
        pathSum(node.right, target - node.val, currentPath, result);
        currentPath.remove(currentPath.size() - 1);
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

递归函数调用次数：对于每个节点，我们最多会调用一次 pathSum 函数。因此，对于一个有 n 个节点的树，最坏情况下，函数会被调用 n 次。
单次递归调用的时间复杂度：对于每个节点的单次递归调用，我们需要执行常数时间操作，如判断当前节点是否为空、更新当前路径、判断是否为叶子节点以及添加结果等。
综上所述，总的时间复杂度是 O(n)，其中 n 是树中节点的数量。

2. 空间复杂度

递归调用栈：递归调用会使用系统栈来存储每一层递归的信息。在最坏的情况下，树可能是一个完全二叉树，此时递归调用栈的深度为 O(h)，其中 h 是树的高度。
其他空间：除了递归调用栈之外，我们不需要额外的空间来存储节点的信息，因此这部分的空间复杂度是 O(1)。
综上所述，总的空间复杂度是 O(h)，在最坏情况下是 O(n)。