图解LeetCode——437. 路径总和 III

图解LeetCode——437. 路径总和 III一、题目 给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但

一、题目

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二、示例

2.1> 示例 1:

图解LeetCode——437. 路径总和 III

输入】root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出】3
解释】和等于 8 的路径有 3 条,如图所示。

2.2> 示例 2:

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

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -10^9 <= Node.val <= 10^9 
  • -1000 <= targetSum <= 1000 

三、解题思路

根据题意,给出了我们解答此题的一些关键信息:

信息1】“径方向必须是向下”——根据这条信息,我们可以确定遍历操作方向;
信息2】“路径不需要从根节点开始,也不需要在叶子节点结束”——可以随意区间简单构成路径;

根据以上两条信息,我们可以首先先到采用前缀和的方式进行解题,因为前缀和适合解答那种连续、累积和这类题目。那么什么是前缀和呢?我们可以以下图为例,如果有4个节点,分别是10、5、2、1,它的前缀和就分别是10151718

图解LeetCode——437. 路径总和 III

那么我们可以通过前缀和的值来计算任意连续的节点和,比如:

求节点5到节点2之和】可以用前缀和17前缀和10,那么结果就是5
求节点5到节点1之和】可以用前缀和18前缀和10,那么结果就是8

了解了前缀和之后,我们就可以从树的root节点开始遍历,此处我们可以采用前序遍历的方式,那么还有两个细节问题需要解决:

问题1:采用什么数据结构来保存前缀和?

我们可以通过创建Map结构key=前缀和,value=相同前缀和值的数量;

问题2:采用前序遍历计算树节点的前缀和,难免会出现重复节点计算的情况,这个怎么办?

可以通过回溯的方式,将值还原到上一步,避免重复计算。

解题思路就这些了,大家采用:前序遍历+前缀和+回溯这3个思路结合方式解题即可。具体实现,请见下面代码实现部分。

四、代码实现

class Solution {
    private Map<Long, Integer> map;
    private int result = 0, target = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        target = targetSum;
        map = new HashMap();
        map.put(0L, 1);
        dfs(root, root.val);
        return result;
    }
    public void dfs(TreeNode node, long value) {
        result += map.getOrDefault(value - target, 0);
        map.put(value, map.getOrDefault(value, 0) + 1);
        if (node.left != null) dfs(node.left, value + node.left.val);
        if (node.right != null) dfs(node.right, value + node.right.val);
        map.put(value, map.getOrDefault(value, 0) - 1);
    }
}

图解LeetCode——437. 路径总和 III

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

今天的文章图解LeetCode——437. 路径总和 III分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/59620.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注