Рекурсивно искать двоичное дерево

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

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 элемент может присутствовать более чем один раз. Поэтому вам может понадобиться изменить этот код, чтобы получить список всех из них.