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算法深度优先搜索

回答

相关问题