java- BST рекурсивное найти значение

Question

У меня есть дерево BST. Я хочу создать метод, который получает значение и возвращает уровень узла, содержащего его значение (корень = 0), нет такого узла? return -1. Я хотел бы сделать это рекурсивно. этот код прекрасно работает:

private int recursiveContains(BinaryNode node, int searchVal){ 
    int nodeKey = node.nodeKey; 
    if (searchVal < nodeKey){ 
     if (node.leftChild != EMPTY_NODE) 
      return 1 + recursiveContains(node.leftChild, searchVal); 
    }else if (searchVal > nodeKey){ 
     if (node.rightChild != EMPTY_NODE) 
      return 1 + recursiveContains(node.rightChild, searchVal); 
    } 
    return 0; 
} 

НО, только до тех пор, как дерево содержит значение поиска.

Как остановить итерацию и вернуть -1, когда я доберусь до листа и не нашел значение? Возможно ли рекурсия?

Thanks

Answer 1

Вам просто нужно отрегулировать свой последний корпус. Прямо сейчас, если значение не находится в дереве, вы просто возвращаете глубину узла, под которым будет вставлено значение, потому что ваш последний случай равен return 0. Вместо этого вам нужно явно проверить , действительно ли текущий узел является правильным узлом. Если это так, вы можете вернуть 0; в противном случае вы должны вернуть -1. Рекурсивные вызовы затем должны искать это специальное значение и обрабатывать его соответствующим образом.

Я бы, вероятно, поставил эту явную проверку - базовый случай этого запрашиваемого узла - в начале. Затем в конце ваше «провальное» значение (то, что вы возвращаете, если ни одно из других условий не является истинным) равно -1. Таким образом, вы получите что-то вроде этого:

// WARNING: UNTESTED CODE 
if (searchVal == nodeKey) { 
    return 0; 
} else if (searchVal < nodeKey && node.leftChild != EMPTY_NODE) { 
    int childResult = recursiveContains(node.leftChild, searchVal); 
    if (childResult != -1) { // Only use the child result if the value was found. 
     return 1 + childResult; 
    } 
} else if (searchVal > nodeKey && node.rightChild != EMPTY_NODE) { 
    int childResult = recursiveContains(node.rightChild, searchVal); 
    if (childResult != -1) { // Only use the child result if the value was found. 
     return 1 + childResult; 
    } 
} 
// If you haven't returned by now, the value can't be found along this path. 
return -1;