[JAVA] DFS, BFS - 루트 노드에서 말단 노드까지 가장 최단 경로

DFS

- 자식이 2개가 아닌 경우에는 DFS에서 오류가 난다. 

- 연습용 코드

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

    public Node(int val) {
        data = val;
        rt = lt = null;
    }
}
public class Solution {
    Node 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+1,root.rt));
            // 자식이 2개가 아니면 DFS 에서는 말단 노드가 아닌 것이 출력되는 오류가 난다.
        }
    }

 

BFS

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

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

public class Solution {
    Node root;
    public int BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root); // 큐에 루트 넣어준다.
        int L = 0; // 레벨은 0 부터
        while(!Q.isEmpty()){
            int len = Q.size(); // 레벨에 있는 원소 개수 = 큐의 사이즈
            for(int i=0; i<len; i++){
                Node current = Q.poll(); // 현재 (레벨) 큐에 있는 원소들
                if(current.lt==null && current.rt == null){
                    return L; // 말단노드의 경우 출력
                }
                // 자식 노드가 있는 경우 현재 노드의 자식 노드를 큐에 넣어준다.
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝남 = 레벨 증가
            L++;
        }
        return 0;
    }