DFS_말단 노드까지 최단 거리 구하기

✅ DFS로 말단 노드까지 최단 거리 구하기

⭐️⭐️⭐️ DFS로 노드까지 최단 거리를 구할 때는 반드시 자식 노드가 2개 다 있어야 한다.

class Node{
    int data;
    Node lt;
    Node rt;

    public Node(int value){
        data=value;
        lt=rt=null;
    }
}

class Main {
    Node root;

    public int DFS(int L, Node root){
        if(root.lt==null && root.rt==null) return L;
        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));


    }
}
//⭐️output:
//1

🔵 ThingsILearned

1️. DFS(0, 1) 호출 - DFS(0, 1)은 lt, rt가 null이 아니므로

- `else`로 넘어감 <br>

1. ` Math.min(DFS(1, root.lt), DFS(1, root.rt))` 호출
   

   • 즉, DFS(1, 2), DFS(1, 3) 호출
     

• DFS(1, 2)는 은 lt, rt가 null이 아니므로
  

  • ` Math.min(DFS(2, root.lt), DFS(2, root.rt))` 호출
    
  • 즉, DFS(2, 4), DFS(2, 5) 호출
    

1. DFS(2, 4)는 lt, rt가 null이다.
   
2. DFS(2, 5)는 lt, rt가 null이다.
   
   • 모두 2를 return
     
   • Math.min(2, 2) = 2 이므로
     
   • DFS(1, 2)은 2를 return한 셈이 된다.
     
3. DFS(1, 3)은 lt, rt가 null이므로
   
   • 1을 return
     

• Math.min(2, 1) = 1이므로
  
• tree.DFS(0, tree.root)의 결과는 1이다.
  

⭐️ L이 static이 아니고 local variable인 이유

이 문제의 경우 L은 static
L은 DFS()의 parameter이다.
이로써 재귀함수가 실행될 때마다 독립적으로 증가된다.
만약 L이 static이었다면 재귀함수 모두가 L을 공유하고, 각 깊이마다 계산되는게 아니라
globally shared across all recursive calls했을 것이다.
따라서 L은 DFS함수의 argument로 작용해야 한다.