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

 

설명

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

 

 

 

예시

1

2        3

4 5

 

가장 짧은 길이는 3번 노느까지의 길이인 1이다.

 

 

 

 

풀이

1. 말단 노드까지 가는데 최소 횟수는 BFS를 사용해서 구한다.

 

2. cur.lt==null 이고 cur.rt==null이면 현재 말단노드이므로 level을 리턴한다.이외의 경우에는 자식을 다시 큐에다가 넣어주면 된다.

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 BFS(Node root) {
    	Queue<Node> queue= new LinkedList<>();
    	queue.add(root);
    	int level=0;
    	
    	while(!queue.isEmpty()) {
    		int size=queue.size();
    		
    		for(int i=0; i<size; 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 0;
    }
  
    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.BFS(tree.root)); 
    } 
}