LeetCode Sum of Paths III 解法for循环反向遍历原因咨询

前置逻辑说明 #

这段代码采用前序遍历+路径回溯的思路实现：

• currPath存储的是从根节点到当前遍历节点的完整路径，节点顺序为[根节点, 二级节点, ..., 当前节点的父节点, 当前节点]
• 每次走到新节点时，仅统计终点为当前节点的合法路径，避免重复计数

反向遍历的设计逻辑 #

for i in range(len(currPath)-1,-1,-1)是从当前节点（currPath最后一位）往根节点的方向倒序遍历，天然适配我们的统计需求：

• 倒序累加currPath[i]的过程，就是在枚举所有「起点为i位置节点、终点为当前节点」的向下路径，完全符合二叉树路径的方向要求
• 每累加一个节点得到的和，刚好对应这条路径的总和，判断是否等于目标值就可以直接计数

举个直观例子：假设当前currPath = [10,5,-3,3]，当前节点是最后一位的3，倒序遍历的枚举结果为：

• i=3：累加和=3 → 对应路径[3]
• i=2：累加和=3+(-3)=0 → 对应路径[-3,3]
• i=1：累加和=0+5=5 → 对应路径[5,-3,3]
• i=0：累加和=5+10=15 → 对应路径[10,5,-3,3]

所有终点为当前节点的路径都被完整枚举，没有遗漏也没有重复。

正序遍历的问题 #

如果把循环改成从根节点往当前节点的正序遍历，累加得到的是「起点为根节点、终点为i位置节点」的路径和，只会统计到以根为起点的路径，所有中间节点作为起点的路径都会被遗漏，最终得到的计数结果远小于正确值。

还是以上面的currPath = [10,5,-3,3]为例，正序遍历的枚举结果为：

• i=0：累加和=10 → 对应路径[10]
• i=1：累加和=15 → 对应路径[10,5]
• i=2：累加和=12 → 对应路径[10,5,-3]
• i=3：累加和=15 → 对应路径[10,5,-3,3]

可以看到除了全路径之外，其他3条终点为当前节点的路径都没有被统计到，无法满足题目要求。

内容的提问来源于stack exchange，提问作者Ragesh Kr