☆打卡算法☆LeetCode 113、路径总和 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个二叉树根节点和目标整数，找出所有符合从根节点到目标节点的值等于目标值的路径。”

题目链接：

来源：力扣（LeetCode）

链接： 113. 路径总和 II

2、题目描述

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 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
输出： []

二、解题

1、思路分析

这道题是112题的升级款，112是找出是否存在这种一条从根节点到目标节点的路径的值之和等于目标值，这道题是找出所有符合要求的路径。

凡是这种题意中要求找出所有答案的都可以试着用深度或广度优先搜索算法去解题。

对于这道题来说，就可以采用深度优先搜索的方式，枚举每一条从根节点到根节点的路径。

对树进行一次遍历，在遍历的时候记录从根节点到当前节点的路径和，防止重复计算。

当遍历到某个节点时，路径和为木棉标志，就找到了一条满足条件的路径。

2、代码实现

代码参考：

class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

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

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
}

3、时间复杂度

时间复杂度 ： O(N²)

其中N是树的节点数，最好情况下，从根节点到每一个子节点的路径都符合题意，此时路径的数目为O(N)，并且每一条路径的节点个数也是O(N)，那么总时间复杂度就是O(N²)。

空间复杂度： O(N)

其中N是树的节点数，空间复杂度取决于队列的开销，队列中的元素个数不会超过树的节点数。

三、总结

这道题是使用了深度优先搜索算法，还可以使用广度优先搜索方法。

使用广度优先搜索的方式，遍历整棵树，找到目标路径。

然后使用哈希表记录树中每个节点的父节点，找到满足条件的节点，就从该节点不断向父节点迭代，即可还原从根节点到当前节点的路径。