말단 노드까지의 가장 짧은 경로

이진트리에서 루트 노드에서 말단 노드까지의 거리 중 제일 짧은 거리를 구하는 문제

노드 1~5가 있을때 트리가 완전이진트리가 아닌 상태

DFS로 구해보면 노드 클래스를 만들고 위의 그림대로 루트,lt,rt를 설정해준다

루트 노드에서 아래로 뻗어가는 레벨이 제일 작은 노드를 구하기 위해서 dfs 함수에 인자로 레벨을 전달해줘서

lt,rt가 모두 없으면 리턴을, 아니면 레벨을 증가시킨 dfs 함수를 재귀로 반복해 lt와 rt의 레벨 중 작은 것을 리턴해준다

 

public int dfs(int L, Node root){
        //트리의 마지막 노드면 노드의 레벨을 리턴
        if(root.lt == null && root.rt == null) return L;
        //Math.min으로 하면 dfs로 재귀를 돌다가 더 작은 값이 리턴되고
        //리턴된 작은 값을 다시 비교해서 작은 값이 리턴되는 방식으로 거슬러 올라온다
        else return Math.min(dfs(L+1, root.lt),dfs(L+1, root.rt));
    }

 

전체 코드 

 

import java.util.*;

class Node{
    int data;
    Node lt, rt;
    public Node(int init){
        data = init;
        lt = rt = null;
    }
}

public class Main{
    Node root;
    public int dfs(int L, Node root){
        //트리의 마지막 노드면 노드의 레벨을 리턴
        if(root.lt == null && root.rt == null) return L;
        //Math.min으로 하면 dfs로 재귀를 돌다가 더 작은 값이 리턴되고
        //리턴된 작은 값을 다시 비교해서 작은 값이 리턴되는 방식으로 거슬러 올라온다
        else return Math.min(dfs(L+1, root.lt),dfs(L+1, root.rt));
    }


    public static void main(String args[]) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        T.root = new Node(1);
        T.root.lt = new Node(2);
        T.root.rt = new Node(3);
        T.root.lt.lt = new Node(4);
        T.root.lt.rt = new Node(5);
        System.out.print(T.dfs(0, T.root));
    }
}

 

bfs를 이용해서 말단 노드 구하기

 

최단 거리는 bfs로 순회하는게 좋다

이진트리를 탐색하면서 양쪽 노드가 모두 없으면 그 노드의 레벨을 리턴한다

public int bfs(Node root){
        Queue<Node> q= new LinkedList<>();
        q.offer(root);
        int L = 0;
        while (!q.isEmpty()){
            int len = q.size();
            for (int i = 0; i < len; i++){
                Node tmp = q.poll();
                if(tmp.lt == null && tmp.rt == null) return L;
                else {
                    if(tmp.lt != null) q.offer(tmp.lt);
                    if (tmp.rt != null) q.offer(tmp.rt);
                }
            }
            L++;
        }
        return L;
    }