BST에서 최소값을 반환하는 재귀 함수를 작성하는 방법은 무엇입니까?

Question

이진 탐색 트리에서 최소값을 반환하는 재귀 함수를 작성하려고합니다.

int RecursiveFindMin(Tree t) { 
    if (t==NULL) 
    return -1; 
    else { 
    if (t!=NULL) 
     RecursiveFindMin(t->left); 
    } 

    return t->val; 
} 

나는

대신 BST에 최소 값을 얻을 것으로 예상, 나는 두 번째 작은 결과를 얻고, 대부분의 시간! 재귀 함수가 좋지 않아 도움을 주시면 감사하겠습니다.

Answer 1

함수에 대한 재귀 호출을 수행하면 반환 값을 무시합니다. 그래서 재귀는 효과적으로 아무것도하지 않습니다. 전달중인 첫 번째 노드의 값이 반환됩니다.

올바른 종료 조건도 사용하고 있지 않습니다. 현재 노드가 NULL 일 때 멈추고 싶지는 않습니다. 왜냐하면 이 왼쪽 일 경우 노드가 NULL 일 때입니다. 그러면 원하는 값이 해당 노드에 있습니다.

그래서 왼쪽 노드를 확인하기 위해 조건을 변경하고, 재귀 호출의 값을 반환 :

int RecursiveFindMin(Tree t) { 
    if (t->left==NULL) 
    return t->val; 
    else { 
    return RecursiveFindMin(t->left); 
    } 
} 

Answer 2

당신은 모든 왼쪽 노드 값을 반환됩니다. 그래서 마침내 루트 값을 반환합니다. 가장 왼쪽의 노드를 찾아서 그 값을 최소값으로 고정해야합니다.

const int kInf = 100000000; 
int RecursiveFindMin(Tree t) { 
    if (t == NULL) return kInf; 
    int v = RecursiveFindMin(t->left); 
    return v == kInf? t->val : v; 
} 

kInf을 트리에없는 값으로 사용했습니다.