路径总和 III - Leetcode

Question

给定目标总和，我们需要找到路径数，即路径总数。又给出了，路径不一定要从根节点开始。

对于这个问题，我找到了一个解决方案。我也能看懂85%的解法

解决方案：

def pathCounter(node,currPath,_sum):
    if node is None:
        return 0
    path = []
    currPath.append(node.data)
    
    pathSum , pathCount = 0, 0
      
    #Unable to understand below for loop
    for i in range(len(currPath)-1,-1,-1):
        
        pathSum +=currPath[i]
        path.append(currPath[i])
        
        
        if pathSum==_sum:
            pathCount+=1
            #print(path)
            
    pathCount+= pathCounter(node.left,currPath,_sum)
    pathCount+= pathCounter(node.right,currPath,_sum)
    
    del currPath[-1]
    
    
    return pathCount

我遇到的问题是，我无法理解为什么 for 循环设置为逆序而不是正常顺序迭代？

这对问题有何影响？

Answer 1

原因是当你在正向执行循环时，if 条件将检查代表 prefix 的总和 currPath，而不是 postfix.

由于递归 在 currPath 末尾追加 节点值，因此重复检查前缀和是没有意义的（因为已经检查过了较早前）。前缀和总是包括根节点（的值），而我们不能假设根节点必须包含在解决方案中。

递归的目的是在所有和检查中包含新访问的节点，并且由于该新节点位于currPath的末尾，总和应从末尾向后累加。

例如：

假设树中有一条向下的路径，其值为：10 - 5 - 3 - 1，我们需要求和 8。然后在第一级递归中，我们访问 10，接下来我们访问 5。此时我们验证这些总和：

* 5
* 5 + 10

都没有给出匹配项，所以我们更深入地重复并访问 3。现在我们检查这些总和：

* 3
* 3 + 5 => It's a match!
* 3 + 5 + 10

如果在这个阶段我们会做一个正向循环，我们会检查这些总和：

* 10
* 10 + 5
* 10 + 5 + 3

None 会匹配，我们永远不会检查不包含根的任何总和。

路径总和 III - Leetcode

Sum of paths III - Leetcode

python

algorithm

binary-tree