루트에서 리프까지의 최단 경로

Question

BST(이진 검색 트리)에서 가장 짧은 루트-리프 경로를 찾는 가장 쉬운 방법(재귀를 사용하는 것이 좋음)은 무엇입니까?Java가 선호되며 의사 코드도 괜찮습니다.

감사해요!

Answer 1

일반적인 설명:

사용 너비 우선 검색(BFS) 반대로 깊이 우선 검색(DFS).자식이 없는 첫 번째 노드를 찾습니다.

DFS를 사용하면 일부 입력 트리에서 운이 좋을 수도 있습니다(그러나 운이 좋았는지 알 방법이 없으므로 여전히 전체 트리를 검색해야 함). 그러나 BFS 방법을 사용하는 것이 훨씬 빠르며 모든 것을 건드리지 않고도 솔루션을 찾을 수 있습니다. 노드.

루트에서 리프까지의 경로를 찾으려면 상위 참조를 사용하여 처음으로 발견된 하위 노드를 따라 루트까지 백업할 수 있습니다.각 노드에 저장된 상위 참조가 없으면 아래로 재귀하면서 상위 노드를 추적할 수 있습니다.목록이 역순으로 있으면 스택에 모두 밀어 넣은 다음 꺼낼 수 있습니다.

의사 코드:

문제는 매우 간단합니다.다음은 가장 작은 길이를 찾는 의사 코드입니다.

1. 루트 노드를 대기열에 넣습니다.

대기열이 비어 있지 않고 결과가 없을 때 반복합니다.

2. 대기열의 시작 부분에서 노드를 가져와서 자식이 없는지 확인합니다.자녀가 없다면 당신은 가장 짧은 길을 찾았습니다.
3. 그렇지 않으면 모든 하위 항목(왼쪽, 오른쪽)을 대기열로 푸시합니다.

모든 최단 경로 찾기:

모든 최단 경로를 찾으려면 대기열 내부의 노드와 함께 노드의 깊이를 저장할 수 있습니다.그런 다음 동일한 깊이를 가진 대기열의 모든 노드에 대해 알고리즘을 계속합니다.

대안:

대신 DFS를 사용하기로 결정했다면 최단 경로를 찾기 위해 전체 트리를 검색해야 합니다.하지만 지금까지 가장 짧은 값을 유지하고 새로운 가장 짧은 값을 찾을 때까지 또는 지금까지 가장 짧은 값에 도달할 때까지 미래 노드의 깊이만 확인하여 최적화할 수 있습니다.하지만 BFS가 훨씬 더 나은 솔루션입니다.

Answer 2

이것은 C++로 되어 있지만 너무 간단해서 쉽게 변환할 수 있습니다.최대 트리 깊이를 얻으려면 min을 max로 변경하십시오.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

이것이 수행하는 작업을 설명하기 위해 리프 노드부터 계산하고(리프를 찾으면 0을 반환함) 다시 루트까지 계산합니다.트리의 왼쪽과 오른쪽에 대해 이 작업을 수행하고 최소값을 취하면 최단 경로가 제공됩니다.

Answer 3

너비 우선 검색은 방문한 정점 수 측면에서 최적입니다.가장 가까운 리프가 있음을 증명하기 위해 폭넓은 우선 검색에서 방문할 모든 정점을 방문해야 합니다.

그러나 재귀를 사용해야 하는 경우 Mike Thompson의 접근 방식은 다음과 같습니다. 거의 사용하기에 적합한 것이며 약간 더 간단합니다.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple(TreeNode 루트){

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}