Q. 개념

---

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를
구하는 프로그램을 작성하세요.
각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를
길이로 하겠습니다.

가장 짧은 길이는 3번 노느까지의 길이인 1이다.

전략

• "최소 이동 횟수" = 최단 거리 구하기 = 원래는 BFS로 풀어야함
  -> DFS로 풀려면 자식 노드가 1개만 있으면 에러 발생한다. (자식노드는 반드시 2개 or 0개)
• 강의에서 트리 백트래킹하면서 각 노드별 반환값 구하는 부분 잘 보기 ★
  
  각 말단노드에서 리턴하는 값에서 이미 각 말단노드까지의 거리를 구한것이고, 이를 백트레킹하는 과정에서 상위 노드에 더 작은 말단노드까지의 거리를 선별해서 올려주는 것임
  (ex. 노드4와 노드5가 리턴한 각 값의 최소값(2)을, 노드4와 노드5를 호출한 노드2가 리턴한다)

정답

import java.util.*;
class Node{ 
    int data; 
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class Main{ 
    Node root; 
    public int DFS(int L, Node root){ 
        // 말단 노드
        if(root.lt==null && root.rt==null) return L;
        // 자식이 1개 밖에 없으면 에러 발생
        else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt));
    } 
  
    public static void main(String args[]) { 
        Main tree=new Main(); 
        tree.root=new Node(1); 
        tree.root.lt=new Node(2); 
        tree.root.rt=new Node(3); 
        tree.root.lt.lt=new Node(4); 
        tree.root.lt.rt=new Node(5); 
        System.out.println(tree.DFS(0, tree.root)); 
    } 
}