递归搜索二叉树

Question

我应该从二叉树中搜索给定的专辑并 return 它。这是我目前拥有的：

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;
}

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

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
    }
}

Answer 2

代码应捕获结果为：

的节点

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

在 Binary Tree 的情况下，一个项目可以出现多次。因此，您可能需要修改此代码以捕获所有这些列表。

递归搜索二叉树

Recursively search binary tree

java

algorithm

graph

binary-search-tree

data-structures