노드 최단거리 (DFS, BFS)

private static class Node{
    int data;
    Node lt, rt;

    public Node(int val){
        this.data = val;
        lt = rt = null;
    }
}

public static void main(String[] args) {
    Node 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);
    int solution = solutionByBFS(root);
    System.out.println(solution);

    int i = solutionByDFS(0, root);
    System.out.println(i);
}

private static int solutionByDFS(int L, Node root){
    if(root.lt == null && root.rt == null){
        return L;
    }else{
        // 노드 양쪽중 한쪽만 있는 경우에는 에러가 발생한다.
        return Math.min(solutionByDFS(L + 1, root.lt), solutionByDFS(L + 1, root.rt));
    }
}

private static int solutionByBFS(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    int minLength = 0;  // 최단 길이
    int queueLen = 0;   // 현재 상태에서의 큐 길이

    while(!queue.isEmpty()){
        queueLen = queue.size();

        // queue.size()로 작업시 for문 내에서 queue에 값이 추가되면 Level 값이 변경되지 않으므로 작업전 길이만큼 반복문을 수행
        for (int i = 0; i < queueLen; i++) {
            Node node = queue.poll();

            if(node.rt == null && node.lt == null){
                return minLength;
            }

            if(node.rt != null){
                queue.offer(node.rt);
            }

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

        minLength++;
    }

    return minLength;
}