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

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

⭐️⭐️⭐️ BFS로 노드까지 최단 거리를 구할 때는 자식 노드가 2개일 필요는 없다.

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

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

class Main {
    Node root;
    public int BFS(int L, Node root) {
        Queue<Node> Q= new LinkedList();
        Q.offer(root);

        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; //여기까지 안 오지만 return값이 int라서 아무 숫자나 return
    }
    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.BFS(0, tree.root));


    }
}

//⭐️output:
//1

🔵 ThingsILearned

✔️ BFS는 Queue쓰니까 Queue하나 만들고
✔️ 같은 레벨에 있는 모든 노드를 돈 다음에 그 다음 레벨로 가니까 Queue 사이즈 만큼 for문을 돈다.
✔️ 그리고 지금 Queue에 자식 노드가 없으면 지금 레벨 리턴
✔️ 왼쪽 자식 노드 있으면 왼쪽 자식 Queue에 추가, 오른쪽 자식 노드 있으면 오른쪽 자식 Queue에 추가