[DFS,BFS] Tree말단 노드까지의 가장 짧은 경로 .java

아래 그림과 같은 이진트리에서 루트 노드 에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요.

각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선에지의 개수를 길이로 하겠습니다.

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

 

내 풀이 - DFS

 

Math.min(오른쪽 자식, 왼쪽 자식)

=> 두 값 중에 가장 짧은 길이를 받아와야함 => 리턴 받는 노드 : 2

=> 노드 3은 리턴 값이 1

=> 노드 1은 노드 2의 값 2와 노드 3의 값 1중 최솟값으로 노드 3의 값인 1이 정답

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


class Node{
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class Main {
    Node root;

    public static int dfs(int L, Node root) {//말단노드에서의 L값을 반환
        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.print(tree.dfs(0,tree.root));


    }

}

 

 

내 풀이 - BFS -> 최단거리

• 자식이 없으면 말단 노드 => L 리턴
• 자식이 있으면 큐에 넣기

 

import java.util.Scanner;


class Node{
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class Main {
    Node root;

    public static int bfs(Node root) {//말단노드에서의 L값을 반환
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int L =0;
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Node cur = q.poll();
                if(cur.lt == null && cur.rt == null) {//말단노드면
                    return L;
                }
                if(cur.lt != null) q.offer(cur.lt);
                if(cur.rt != null) q.offer(cur.rt);
            }
            L++;
        }
        return 0;


    }
    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.print(tree.bfs(tree.root));


    }

}