迭代DFS如何遍历？
以下程序找到总和给定数字的路径。迭代DFS如何遍历？
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。我理解程序的大部分内容，但我不知道如果到达叶节点，它是如何遍历的。
我想唯一的回溯方式是调用每个节点的函数。这就是我们称之为迭代的原因。我的理解是否正确和完整？或者更确切地说，我们不会回溯。我们只是从一个新的子节点开始。
如果这是真的，那么我们通过重新探访许多路径而浪费时间，是不是？
Here您可以看到迭代加深搜索的工作原理。
它以与深度优先搜索相同的顺序访问搜索树中的节点，但首次访问节点的累积顺序实际上是宽度优先的。
它返回到根节点并增加搜索深度。
在上面的PROGRAMM我觉得和值定义的算法将在多大程度上搜索从根开始node.So我想穿越回去，你应该有相同的根值，总和值增加再次调用该函数。
我认为通过查看算法执行时堆栈中的哪些节点会更容易看到发生了什么。例如，让我们假设，我们有这个树：
A
/\
B C
/\
D E
我们开始用含堆栈：
A
/\
B C Stack: A
/\
D E
我们弹出一个出栈并推动B和C：
A
/\
B C Stack: B, C
/\
D E
现在，我们弹出ç出栈，推动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没有孩子，所以我们将它从堆栈中弹出并且探索终止。
希望这可以让你了解备份是如何发生的 - 当许多节点被推入堆栈时，只有其中一个被探测，其余的被推迟到以后的时间。然后通过“跳回”到先前被发现但未被访问的另一节点隐含地实施备份。
您在这里的具体DFS代码会在每个级别进行一些额外的处理以跟踪余下的总和，并且我将把它作为练习留给读者看看它是如何工作的。
同时，请注意，通过代码跟踪这样的图片往往是找出实际代码片段的最佳方式。单独阅读代码并查看其效果非常困难，但通过绘制正确的图片，其执行和行为可以变得更清晰。
我不相信这段代码会使用迭代加深，并且总和只会在它碰到叶子时发挥作用，所以我不确定您提供的链接或您在此处包含的解释是否与这个问题。 – templatetypedef