section7.9

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

 

 

 

ANSWER

public class Question9 {
    Node root;

    public static void main(String[] args) {
        Question9 tree = new Question9();
        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.rt.rt = new Node(5);
        System.out.println(tree.BFS(tree.root));
    }

    public int BFS(Node root) {
        int level = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node cur = queue.poll();
                if (cur.lt == null || cur.rt == null) {
                    return level;
                }

                if (cur.lt != null) {
                    queue.offer(cur.lt);
                }

                if (cur.rt != null) {
                    queue.offer(cur.rt);
                }
            }
            level++;
        }
        return 0;
    }
}

• 자식 노드 중 하나라도 없으면 그때 레벨 return 하면 될 것 같아서 앞에 코드 참고해서 작성했다 답은 제대로 나오는데 정답인지는 모르겠네 

 

 

 

SOLUTION

// 1. DFS 풀이
public class Answer9V1DFS {
    Node root;

    public static void main(String[] args) {
        Answer9V1DFS tree = new Answer9V1DFS();
        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.rt.rt = new Node(5);
        System.out.println(tree.DFS(0, tree.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+2, root.rt));
        }
    }
}

// 2. BFS 풀이
public class Answer9V2BFS {
    Node root;

    public static void main(String[] args) {
        Answer9V2BFS tree = new Answer9V2BFS();
        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.rt.rt = new Node(5);
        System.out.println(tree.BFS(tree.root));
    }

    public int BFS(Node root) {
        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 L;
    }
}

• "최단 거리"이기 때문에 BFS로 풀어야 하는 문제