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

 

원래는 BFS로 푸는 문제인데 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 Level, Node root) {
		
		if(root.lt == null && root.rt == null) {
			return Level;
		}else {
			return Math.min(DFS(Level+1, root.lt), DFS(Level+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));
	}
}

 

2. BFS

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> Q = new LinkedList<>();
		Q.offer(root);
		int Level = 0;
		while(!Q.isEmpty()) {
			int len=Q.size();
			for(int i=0; i<len; i++) {
				Node cur = Q.poll();
				// 말단노드
				if(cur.lt == null && cur.rt == null) {
					return Level;
				}
				if(cur.lt != null) {
					Q.offer(cur.lt);
				}
				if(cur.rt !=null) {
					Q.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));
	}
}