★9. 말단 노드까지 최소 간선 DFS

1. 문제

말단 노드 중에서 간선의 길이가 가장 짧은 길이를 출력하시오.

 

 

2. 나

강의 보고 진행

 

3 - 1. 강의 풀이

강의에서는 완전 이진트리에서만 풀이가 가능하다는 전제를 세웠다.

양 쪽 자식노드가 null이면 말단 노드라는 뜻이므로 해당 계층 L을 리턴한다.

해당 L은 옆에있는 노드의 말단 노드의 계층과 min으로 비교되어서 리턴된다.

 

커뮤니티에서 불완전 이진트리에 대한 풀이도 있다.

 

 

 

 

 

3 - 2. 강의 코드

완전 이진트리

package BFS_DFS;
import java.util.*;


class Node {
    int data;
    Node lt, rt;

    Node(int value) {
        this.data = value;
    }

}

public class dfs09 {
    static Node root;

    public static 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) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);


        System.out.println(DFS(0,root));
    }
}

 

불완전 이진트리

package BFS_DFS;
import java.util.*;

class Node {
    int data;
    Node lt, rt;

    Node(int value) {
        this.data = value;
    }

}

public class dfs09 {
    static Node root;

    public static int DFS(int L,Node root) {
        if (root == null || (root.lt == null && root.rt == null)) {
            return L;
        } else return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt));
		//불완전 이진트리인 root 노드가 root.lt, root.rt를 호출할 때
        //root ==null에 걸려서 해당 계층을 바로 리턴하게된다.
    }

    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);


        System.out.println(DFS(0,root));
    }
}

 

4. 얻어갈 점

불완전 이진트리를 중심으로 알아가면 많은 도움이 될 듯.

꼭 그려보면서 흐름을 익히자.