Ruby递归DFS方法 [英] Ruby recursive DFS method

问题描述

对于深度优先搜索算法实现的递归方法，我有些麻烦。这是二叉树的照片：

I have some troubles with recursive method for depth first search algorithm implementation. Here's the binary tree photo:

该方法在树的右侧效果很好（55、89、144），但是在左侧时返回nil，即使它放置是。那么，代码有什么问题呢？该节点是Node类的一个实例，该实例具有值（整数），并链接到左右子节点（Node类的其他实例），如果该子节点没有该侧的子节点，则该节点为nil。

The method works well with the right side of the tree (55, 89, 144), but it returns nil when it comes to the left side, even though it puts "yes". So, what's wrong with the code? The node is an instance of Node class that has value (integer) and links to the left and right child (other instances of Node class) which is nil if it doesn't have the child from that side.

这是方法代码：

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

推荐答案

由于 depth_first_search（node.child_left，target）不是方法的最后一行，因此永远不会返回其值。如果其值不是 nil ，则需要返回它的值。这是解决问题的一种方法的示例：

Because depth_first_search(node.child_left, target) isn't the last line of your method, its value will never be returned. You need to return its value if its value is not nil. Here is an example of one way to solve your problem:

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

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

Note that this example will search the right subtree even if the correct node is found on the left subtree, which is inefficient.

这篇关于Ruby递归DFS方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！