java- BST 재귀 값 찾기

Question

BST 트리가 있습니다. 값을 가져 와서 그 값 (root = 0)을 포함하는 노드의 레벨을 반환하는 메소드를 만들고 싶습니다. 그런 노드는 없습니까? -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을 반환하고 값을 찾지 못했습니까? 재귀가 가능합니까?

감사합니다.

Answer 1

최종 케이스를 조정하면됩니다. 현재 값이 트리에 없으면 값이 삽입 될 노드의 깊이를 반환합니다. 마지막 사례는 단지 return 0이므로 대신 현재 노드가 실제로 올바른 노드인지 확인하려면 을 확인해야합니다.. 그럴 경우 0을 반환 할 수 있습니다. 그렇지 않으면 -1을 반환해야합니다. 그런 다음 재귀 호출은 해당 특수 값을 찾고 적절하게 처리해야합니다.

저는이 명시적인 확인을 할 것입니다.이 기본 케이스는 요청 된 노드입니다. 그런 다음 마지막에 "fall-through"값 (다른 조건이없는 경우 반환 값)은 -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;