路径和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条件将检查表示currPath的前修复的和，而不是后修复

由于递归在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

没有匹配的，我们也不会检查任何不包含根的总和