[알고리즘]BFS - Tree 말단 노드까지의 가장 짧은 경로

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램

 

 

import java.util.LinkedList;
import java.util.Queue;

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.offer(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));
	}

}

---

1