Tree노드까지의 말단경로-알고리즘

위 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하시오.
각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.

접근법

우선 DFS와 BFS를 이용한 문제풀기이다. 이 문제는 Level의 깊이를 구하는 문제이기 때문에 모든 노드를 탐색하는 DFS보다는 한 단계씩 파악하는 BFS로 푸는 것이 좋은 방법이다.

보통 DFS는 Recursion을 이용해서 해결할 수 있고,
    BFS는 Queue를 통해 해결할 수 있다. 
    

1. DFS로 푼다면 모든 노드를 다 순회한 후에 깊이 중 최솟값을 변수에 저장하여 리턴하면된다.

2. BFS로 푼다면 다음 자식노드가 존재하지 않을 때 LEVEL을 순회했기 때문에 그때 리턴하면 된다.

코드

BFS

    public static void solution(){

        Node node = new Node(1);
        node.lt = new Node(2);
        node.rt = new Node(3);
        node.lt.lt = new Node(4);
        node.lt.rt = new Node(5);


        System.out.println(BFS(node));
    }

    public static int BFS(Node node){
        Queue<Node> queue = new LinkedList<>();

        queue.offer(node);
        int level = 0;

        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 -1;
    }


    public static class Node{
        private int root;
        private Node lt,rt;
        public Node(int root){
            this.root = root;
            lt = null;
            rt = null;
        }


    }

DFS

public static void solution(){

        Node node = new Node(1);
        node.lt = new Node(2);
        node.rt = new Node(3);
        node.lt.lt = new Node(4);
        node.lt.rt = new Node(5);

        System.out.println(DFS(0,node));
    }

    public static int DFS(int level, Node node){

        if(node.lt==null && node.rt==null){
            return level;
        }else {
            return Math.min(DFS(level+1, node.lt),DFS(level+1, node.rt));
        }

    }

    private static class Node{
        private int root;
        private Node rt,lt;
        public Node(int root){
            this.root = root;
            lt = null;
            rt = null;
        }


    }