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)不是方法的最后一行,所以永远不会返回它的值.如果值不是,则需要返回其值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

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