Ruby递归DFS方法

Question

我在实现深度优先搜索算法的递归方法时遇到了一些问题。以下是二叉树的照片： 该方法对树的右侧（55、89、144）有效，但当涉及到左侧时，它返回nil，尽管它输出了“yes”。那么，代码有什么问题呢？节点是Node类的实例，具有值（整数）和指向左右子节点的链接（其他Node类的实例），如果不从该侧具有子节点，则为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

- poctek

Answer 1

因为depth_first_search(node.child_left, target)不是你的方法的最后一行，所以它的值永远不会被返回。如果它的值不是nil，那么你需要返回它的值。下面是解决问题的一种方式的示例:

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

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

- Adrian