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

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오.

 

가장 짧은 경로를 DFS로 푸는건 매우 비효율적이나 학습을 위한 문제풀이임.

 

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

    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.DFS(0, tree.root));
    }

}