java - 递归搜索二叉树

Question

我应该从二叉树中搜索给定的专辑并将其返回。这是我到目前为止所拥有的:

public AlbumNode getAlbum(AlbumNode root, String name) {
    if (root != null) {
        if(root.left != null) getAlbum(root.left, name);
        if(root.right != null) getAlbum(root.right, name);
    }
    if(root.getName().equals(name)) return root;

    return null;
}

我知道问题出在哪里(我想)，但我卡住了......在获得所有节点的名称后，它将它们与名称进行比较，但它对所有节点都这样做并返回最后一个检查(它始终是二叉树的根)。我该如何解决这个问题？

Answer 1

试试这段代码:

public AlbumNode getAlbum(AlbumNode node, String name) {
    if (node == null) {     // this checks the base case
        return null;        // your original code failed for a null root
    } else {
        if (node.getName().equals(name)) {
            return node;
        } else {
            AlbumNode result = getAlbum(node.left, name);
            if (result != null) {
                return result;
            }
            result = getAlbum(node.right, name);

            return result;  // you need to return the result inside the recursion
        }                   // your original code never returned the recursive calls
    }
}