이진 검색 트리에서 리프에 대한 최단 경로

Question

재귀를 사용하여 BST (이진 검색 트리)에서 최단 경로를 찾았습니다. 최단 경로는 발견 된 첫 번째 자식없는 리프 여야합니다. 내가 돌아올 때마다 나는 뿌리를 돌려 준다. 여러 가지 방법을 시도하고 nullPointerException에 대한 루트를 계속 가져옵니다. 여기에 내가

 public int minPath(){ 
    if(isEmpty()){ 
     return -1; 
    } 
    else{ 
     return findMin(root); 
    } 
} 

private int findMin(IntegerTreeNode tNode){ 
    if((tNode.left != null) && (tNode.right != null)){ 
     findMin(tNode.left); 
     findMin(tNode.right); 
    } 
    return tNode.item; 
} 

을 가지고 무엇을 내가 뭘 일어나고 그것이 스택의 시작을 반환이라고 생각합니다, 그래서 어떻게 내가 첫 아이가 잎 노드를 반환?

Answer 1

가중치가없는 지정된 대상에 대한 최단 경로를 찾게되므로 폭 넓은 우선 검색을 사용하여이 문제를 해결할 수 있습니다. 이것은 BST이기 때문에 가중치가 적용되지 않아야하므로 BFS가 여기에서 선택한 알고리즘이됩니다.

여기에 멋진 프리젠 테이션과 의사가 알고리즘의 후속 조치입니다 :

BFS Tutorial

당신의 목표 상태는 자식, 따라서 리프 노드가없는 노드가 될 것입니다. BFS가이 목표에 대한 최단 경로를 찾을 것이므로이 알고리즘은 첫 번째 노드를 반환합니다.

Answer 2

findMin 메서드는 int을 반환하지만 반환 된 int을 사용하지 않고 재귀 호출을하고 있습니다. 재귀 호출의 반환 된 값을 어떻게 활용할 수 있는지 생각하면서 메서드를 다시 디자인 할 것을 권합니다.