Ruby递归DFS方法

Question

我在深度优先搜索算法实现的递归方法方面遇到了一些麻烦。这是二叉树照片：

该方法适用于树的右侧 (55, 89, 144)，但当它到达左侧时 returns nil，即使它放置 "yes"。那么，代码有什么问题呢？该节点是 Node class 的一个实例，它具有值（整数）并链接到左右子节点（Node class 的其他实例），如果它没有来自该节点的子节点，则为 nil边.

方法代码如下：

def depth_first_search(node, target)
    if node.value == target
        puts "yes"
        return node
    end
    depth_first_search(node.child_left, target) if node.child_left
    depth_first_search(node.child_right, target) if node.child_right
end

Answer 1

因为 depth_first_search(node.child_left, target) 不是您方法的最后一行，所以它的值永远不会被 return 编辑。如果它的值不是 nil，你需要 return 它的值。这是解决您的问题的一种方法的示例：

def depth_first_search(node, target)
    if node.value == target
        puts "yes"
        return node
    end
    left = depth_first_search(node.child_left, target) if node.child_left
    right = depth_first_search(node.child_right, target) if node.child_right
    left or right
end

请注意，即使在左子树上找到了正确的节点，此示例也会搜索右子树，这是低效的。

Ruby递归DFS方法

Ruby recursive DFS method

ruby

recursion

ruby-on-rails

depth-first-search