Java算法深度優先搜索

boolean dfs(TreeNode root, int target) { 
     if (root == null) 
      return false; 
     if (root.data == target) 
      return true; 
     return dfs(root.left, target) || dfs(root.right, target); 
    }

在最後一行中實際執行的程序是什麼......任何人都可以請解釋一下。Java算法深度優先搜索

來源

2012-01-31 A15

有趣的是，大多數人完全錯過了如果由於'||'短路而在左子樹中發現「target」，從不探索正確的子樹的事實。 – 2012-01-31 10:27:24

@UMad是真的，但它也是所需的行爲。如果你在左邊的子樹中找到'target'，那麼你就不需要去探索正確的子樹。所以'''短路實際上是好的。 – 2012-01-31 10:37:42

我知道這是需要的和有意的。我在評論最常說明兩個子樹被探索的解釋，而沒有提到對右子樹的探索是有條件的。 – 2012-01-31 11:33:17

它是遞歸探索左分支尋找target然後右分支target。

更具體算法做到這一點：

如果目標是在這個節點找到，返回真
否則，遞歸到左子樹中尋找目標
如果目標是在左子樹那麼遞歸調用將返回true，並在||上進行短路將使該方法立即返回
else else ||表達式中的第二個子表達式被計算，遞歸到右子樹中尋找目標，返回ns布爾表示在右子樹中存在target

來源

2012-01-31 10:18:32

該程序對樹的左右分支應用相同的方法（dfs）並返回兩個結果的「或」。

基本上，如果在當前節點中找不到目標，則檢查它是否可以在左分支或右分支中找到。這是遞歸地應用的，直到沒有剩餘的節點（當它匹配第一個根的情況爲空時）。

你可以在這裏查看我的答案： Recursion - trying to understand 看看它是否有助於理解問題。

來源

2012-01-31 10:18:49 pcalcao

它正在做一個遞歸調用，先探索左邊，然後右邊的子樹。

這意味着它將首先在左邊向下，直到它到達一片葉子，然後回到右邊。

如果它在右子樹的左邊或右邊找到目標，則返回true。

http://en.wikipedia.org/wiki/Depth-first_search

來源

2012-01-31 10:19:06

這是一個遞歸調用，其中dfs首先遍歷所有的節點留給根，然後將所有節點權根和「OR」這兩個調用的結果返回true或false。

來源

2012-01-31 10:20:11 Waqas

最後一行

return dfs(root.left, target) || dfs(root.right, target);

相當於

if (dfs(root.left, target)) { 
    return true; 
} 
return dfs(root.right, target);

換句話說，該方法遞歸地施加到左子樹。只有在返回false時，該方法纔會遞歸應用於右子樹。

來源

2013-04-21 10:58:46 NPE

Java算法深度優先搜索

回答

相關問題