Ruby递归DFS方法

Question

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

该方法在树的右侧（55、89、144）工作得很好，但是当它来到左侧时，它返回nil，即使它输入“是”。那么，代码有什么问题呢？节点是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

Answer 1

因为depth_first_search（node.child_left，target）不是方法的最后一行，所以它的值永远不会返回。如果其值不是＜code＞nil＜/code＞，则需要返回其值。下面是一个解决问题的方法示例：

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

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