재귀를 사용하여 이진 트리 안의 리프 ​​노드에서 가장 긴 경로를 찾을 수 있습니다.

Question

시험에 대한 독학으로 문제가 생겼으며 & 답이 부족하여 문제가 발생했습니다. 운동은 다음과 같이 명시합니다 :

"주어진 2 진 트리의 높이, 즉 루트 노드에서 리프 노드까지의 가장 긴 기존 경로를 계산하기 위해 재귀를 사용하는 알고리즘을 작성하십시오."

메소드의 기본 시작이 제공되며 최종 응답을 구성하려면이 메소드를 수정해야합니다. 이 메서드 밖에서 추가 메서드를 사용할 수 없습니다.

// Binary tree height, find the longest path to a leaf node 
public static int height(BTree t) { 
    return 0; 
} 

각 함수 호출 전에 노드가 트리에 추가됩니다. 최종 주어진 나무는 다음과 같습니다

// Binary tree height, find the longest path to a leaf node 
public static int height(BTree t) { 

    BTreeNode n = t.getRoot(); 

    int height = 0; 
    int calc = 0; 

    if (n == null) 
    { 
     return height; 
    } 
    else 
    { 
     while (n!=null) { 
      n = n.getLeftChild(); 
      calc++; 
     } 
    } 

    if(calc > height) { 
     height = calc-1; 
     height = 0; 
    } 

    n = t.getRoot(); 
    while (n!=null) { 
     n = n.getRightChild(); 
     calc++; 
    } 

    if(calc > height) { 
     height = calc-1; 
     height = 0; 
    } 


    return height; 
} // height() 

은 내가 공부를 도와 모든 도움이 시험을 통과하십시오 :

다음

 10   
    __/ \__  
    5  15 
/\ /\ 
3 8 12 18 
    \  /\  
    4 11 13 

내가 지금까지 가지고 있지만 제대로 작동하지 않는 것입니다 대단히 감사합니다!

Answer 1

이 경우 재귀가 좋은 선택입니다. 높이를 얻으려면 루트 노드와 깊이 0부터 시작하십시오. 최대 깊이를 얻는 함수가 있습니다. 이 함수는 전달 된 노드가 null (트리의 끝)이면 깊이를 반환합니다. 그렇지 않으면 왼쪽 및 오른쪽 자식에 대해 1 씩 증가 된 깊이로 자체를 호출합니다 (즉, 다른 레이어가 있으므로 깊이를 늘려야 함). 그런 다음 더 높은 깊이를 반환합니다. 코드는 다음과 같습니다.

public static int getMaxDepth(BTreeNode node, int depth) { 
    if (node == null) return depth; 
    return Math.max(getMaxDepth(node.getLeftChild(), depth + 1), getMaxDepth(node.getRightChild(), depth + 1)); 
} 

이렇게하면 전체 트리를 따라 가면서 가장 긴 경로를 찾습니다. (이 코드는 테스트하지 않았지만 제대로 작동합니다.)

심도가 더 큰지 확인하는 간단한 if 절을 원한다면 Math.max()을 피할 수 있지만 개인적으로 선호합니다.

재귀를 해결하고 반복으로 대체 할 수도 있습니다. 하지만 더 많은 코드를 작성해야합니다.이 코드는 읽고 이해하기가 더 어려울 것입니다. 재귀가없는 한 가지 방법은 현재 레이어 (및 깊이)의 모든 노드 (예 : ArrayList)를 추적 한 다음 마지막 레이어에서 노드의 모든 자식을 가져 오는 것입니다. 그 후에 발견 된 아이들과 함께 목록을 업데이트하고 깊이를 증가시킵니다. 자식 목록이 비어 있으면 트리의 끝에 도달하여 깊이를 반환 할 수 있습니다. 이 코드는 다음과 같이 표시됩니다 (다시 테스트하지 않음).

public static int getMaxDepth(BTreeNode root) { 
    if (root == null) return 0; 
    List<BTreeNode> currentLayer = new ArrayList<>(); 
    List<BTreeNode> children = new ArrayList<>(); 
    int depth = 0; 

    currentLayer.add(root); 
    while (0 < currentLayer.size()) { 
     depth++; 

     children.clear(); 
     for (BTreeNode node : currentLayer) { 
      BTreeNode left = node.getLeftChild(); 
      if (left != null) children.add(left); 

      BTreeNode right = node.getRightChild(); 
      if (right != null) children.add(right); 
     } 

     currentLayer.clear(); 
     currentLayer.addAll(children); 
    } 

    return depth; 
} 

Answer 2

public int height(BTree t) { 

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

    return 1 + Math.max(height(t.left), height(t.right)); 
}