트리의 최소 경로 찾기

Question

이것은 내 연구 코드에서의 문제이며이를 수행하는 효율적인 방법이 무엇인지 궁금합니다. 나는 불필요한 세부 사항을 생략하고 문제의 핵심이 이해 될 수 있도록 그것을 제시하고있다.

각 노드에 숫자가있는 이진 트리가 있다고 가정 해 보겠습니다. 루트에서 리프로 시작하는 트리의 모든 분기의 최소 합계를 찾고 싶습니다. 아래는 매우 거친 의사 코드입니다.

int minimum(tree){ 
    // Some base cases 
    left_min = minimum(tree->left); 
    right_min= minimum(tree->right); 
    if (left_min < right_min){ 
     return current_value + left_min; 
    } 
    else{ 
     return current_value + right_min; 
    } 
} 

이로부터 최소값을 계산할 수 있습니다. 그러나 최소값을주는 노드를 계산하려면 어떻게해야합니까? 즉 답변이 14 번이라면 트리의 각 레벨에서 어떤 노드가 합쳐져서 14를 합산하는지 알아 내고 싶습니다. 기존 함수를 최소한으로 변경하면서이 작업을 수행하는 효율적인 방법은 무엇입니까? 최소한의 변경으로 분기를 추적하기 위해 변수를 추가 할 수는 있지만 함수를 완전히 다시 작성할 수는 없습니다.

감사

당신은 선택된 노드를 추적하기 위해 추가 인수로 목록/큐를 사용할 수 있습니다

Answer 1

:

typedef vector<yourIdType> idvec; 

int minimum(tree, idvec &path){ 
   // Some base cases 
    idvec leftPath, rightPath; 
    left_min = minimum(tree->left, leftPath); 
   right_min= minimum(tree->right, rightPath); 
   if (left_min < right_min){ 
     swap(path, leftPath); 
     path.push_back(thisNodeId); 
     return current_value + left_min; 
    } else { 
     swap(path, rightPath); 
     path.push_back(thisNodeId); 
     return current_value + right_min; 
   } 
} 

Answer 2

: 당신은 목록을 사용하거나 스택 또는 대신 벡터의 대기 할 수

int minimum(tree, list){ 
    List templeft, tempright; 
    // Some base cases 
    left_min = minimum(tree->left, templeft); 
    right_min= minimum(tree->right, tempright); 
    if (left_min < right_min){ 
     list.push_back(templeft); 
     list.push_back(current); 
     return current_value + left_min; 
    } 
    else{ 
     list.push_back(tempright); 
     list.push_back(current); 
     return current_value + right_min; 
    } 
}