本文主要是介绍力扣-437 路径总和III,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
参考自https://leetcode-cn.com/problems/path-sum-iii/solution/qian-zhui-he-di-gui-hui-su-by-shi-huo-de-xia-tian/
前缀和–是指到达当前元素的路径之前所有元素的和
- 在同一个路径之下,如果两个数的
前缀和是相同的
,那么这些节点之间的元素总和为零- 那么,在同一个路径之下,在节点A的前缀和与节点B的前缀和相差target,则位于节点A和节点B之间的元素之和是target。(如当前已知路径为A->C->B,A和B的前缀和相差target,那么C+B的和就是target)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def pathSum(self, root: TreeNode, sum: int) -> int:num_dict = {}num_dict[0] = 1 # 初始化,前缀和为0的一条路径return self.recursionPathSum(root, num_dict, sum, 0)def recursionPathSum(self, node, num_dict, target, currSum):if (node == None): return 0res = 0currSum += node.val # 当前路径和'''重点:如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了所以根据当前num_dict的值进行搜索,将结果加入res中'''res += num_dict.get(currSum-target, 0)num_dict[currSum] = num_dict.get(currSum, 0)+1res += self.recursionPathSum(node.left, num_dict, target, currSum)res += self.recursionPathSum(node.right, num_dict, target, currSum)num_dict[currSum] -= 1 # 回到本层,去掉本层的路径和return res
这篇关于力扣-437 路径总和III的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!