Tree 말단노드까지의 가장 짧은 경로(BFS)

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오.(최단 거리는 BFS)

 

import java.util.*;

class Node {
    int data;
    Node lt, rt; //자식 노드들의 주솟값
    public Node(int val) {
        data=val;
        lt=rt=null;
    }
}

public class Main {
    Node root;
    public int BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while(!Q.isEmpty()) {
            //레벨의 길이를 구하자!
            int len = Q.size(); //1 2 4 8 ....
            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.println(tree.BFS(tree.root));
    }

}