迭代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。我理解程序的大部分內容，但我不知道如果到達葉節點，它是如何遍歷的。

我想唯一的回溯方式是調用每個節點的函數。這就是我們稱之爲迭代的原因。我的理解是否正確和完整？或者更確切地說，我們不會回溯。我們只是從一個新的子節點開始。

如果這是真的，那麼我們通過重新探訪許多路徑而浪費時間，是不是？

來源

2016-04-25 John Hass

Here您可以看到迭代加深搜索的工作原理。

它以與深度優先搜索相同的順序訪問搜索樹中的節點，但首次訪問節點的累積順序實際上是寬度優先的。

它返回到根節點並增加搜索深度。

在上面的PROGRAMM我覺得和值定義的算法將在多大程度上搜索從根開始node.So我想穿越回去，你應該有相同的根值，總和值增加再次調用該函數。

來源

2016-06-03 08:45:49

我不相信這段代碼會使用迭代加深，並且總和只會在它碰到葉子時發揮作用，所以我不確定您提供的鏈接或您在此處包含的解釋是否與這個問題。 – templatetypedef

我認爲通過查看算法執行時堆棧中的哪些節點會更容易看到發生了什麼。例如，讓我們假設，我們有這個樹：

  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代碼會在每個級別進行一些額外的處理以跟蹤餘下的總和，並且我將把它作爲練習留給讀者看看它是如何工作的。

同時，請注意，通過代碼跟蹤這樣的圖片往往是找出實際代碼片段的最佳方式。單獨閱讀代碼並查看其效果非常困難，但通過繪製正確的圖片，其執行和行爲可以變得更清晰。

來源

2017-06-12 21:49:20 templatetypedef

迭代DFS如何遍歷？

回答

相關問題