以下程序查找总和为给定数字的路径。
def hasPathSum(self, root, sum):
if root is None:
return False
stack = [(root, sum)]
while stack:
node, _sum = stack.pop()
if node.left is node.right is None and node.val == _sum:
return True
if node.left:
stack.append((node.left, _sum - node.val))
if node.right:
stack.append((node.right, _sum - node.val))
return False
它使用带有堆栈的迭代 DFS。我理解程序的大部分内容，但如果到达叶节点，我不知道它如何遍历回来。
我想遍历回去的唯一方法是为每个节点调用函数。这就是我们称之为迭代的原因。我的理解正确和完整吗？或者更准确地说，我们不会向后移动。我们只是从一个新的子节点重新开始。
如果这是真的，那么我们重新审视许多路径是在浪费时间，不是吗？
我认为通过查看算法执行时堆栈上的节点来了解这里发生的事情要容易得多。例如，假设我们有这棵树：
A
/
B C
/
D E
我们从包含 A 的堆栈开始：
A
/
B C Stack: A
/
D E
我们从堆栈中弹出 A 并推动 B 和 C：
A
/
B C Stack: B, C
/
D E
现在，我们从堆栈中弹出 C 并推送 D 和 E：
A
/
B C Stack: B, D, E
/
D E
现在，我们将 E 从堆栈中弹出。在这一点上，我们在一片叶子上，所以我们不会在树上添加更多的东西。
A
/
B C Stack: B, D
/
D E
你问我们目前如何"备份"。这里没有任何明确的东西可以让我们"备份"，而是我们只是从堆栈中弹出下一个节点并继续查找那里。下一个节点是 D，因此我们已经通过 C 有效地备份，现在正在尝试节点 D。
由于 D 也没有子项，我们只需从堆栈中弹出它：
A
/
B C Stack: B
/
D E
堆栈的顶部现在是 B，所以我们隐式地"备份"到 A，然后探索 A 的下一个子项，B .B 没有子级，所以我们将其从堆栈中弹出，探索终止。
希望这能让您了解备份是如何发生的 - 当许多节点被推送到堆栈上时，只探索其中一个节点，其余节点被推迟到以后的时间。然后，通过"跳回"到之前发现但未访问的另一个节点来隐式实现备份。
您在此处拥有的特定 DFS 代码在每个级别进行一些额外的处理，以跟踪剩余的总和，我将把它作为一个练习留给读者，看看它是如何工作的。
但与此同时，请注意，用这样的图片跟踪代码通常是弄清楚一段代码实际作用的最佳方式。很难孤立地阅读代码并看到其效果，但是通过绘制正确的图片，它的执行和行为可以变得更加清晰。
在这里，您可以看到迭代深化搜索如何工作的图像。
它以与深度优先搜索相同的顺序访问搜索树中的节点，但首次访问节点的累积顺序实际上是广度优先。
它返回到根节点并增加搜索的深度。
在上面的程序中，我认为总和值定义了算法从根节点开始搜索的距离。所以我想要遍历回来，你应该使用相同的根值再次调用该函数，并且总和值增加。