java - 使用递归在二叉树中查找包含给定字符串的节点

Question

我有这个方法，它使用递归在二叉树中查找包含指定 String 的节点。问题是它返回 null，而它应该返回包含指定名称的节点，我不确定为什么。

方法如下:

public Node getNode(Node currentNode, String name) { 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null) {
            getNode(currentNode.right, name);
        } 
        if (currentNode.left != null) {
            getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

如果能深入了解问题所在，我们将不胜感激。

Answer 1

您需要捕获两个递归调用的返回值。否则，您将“白费力气”地进行递归并丢弃递归的结果。

public Node getNode(Node currentNode, String name){ 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null){
            retrieved = getNode(currentNode.right, name);
        } 
        if (retrieved == null && currentNode.left != null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

以下解决方案可以说是更好的样式，因为您将 null 检查保留为基本情况。请注意，您不再需要检查 currentNode.right != null 或 currentNode.left != null，因为在又一次递归步骤后它们已被基本情况覆盖.

public static Node getNode(Node currentNode, String name){
    // Base case: currentNode is null, nothing left to search
    if (currentNode == null) {
        return null;
    }

    Node retrieved = null;
    if (currentNode.getName().equals(name)) {
        retrieved = currentNode;
    } else {
        // Try to search right subtree
        retrieved = getNode(currentNode.right, name);

        // If not found in right subtree, then search left subtree
        if (retrieved == null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}