# Java Solution beats 99% using DFS

• ``````public class Solution {
public static class Node{
int num;
int val;
public Node(int num){
this.num = num;
}
}
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
Node[] graph = new Node[n];
for (int i = 0; i < n; i++)
graph[i] = new Node(i);
// build graph
for (int i = 0; i < edges.length; i++) {
int a = edges[i][0];
int b = edges[i][1];
}
boolean[] visited = new boolean[n];
DFS(graph, 0, 0, visited);
Arrays.fill(visited, false);
graph[farest].val = 0;
DFS(graph, farest, 0, visited);
int length = graph[farest].val;
// find the mid
int mid = length / 2;
boolean two = true;
if (length % 2 == 0) {
two = false;
} else {
mid = mid + 1;
}
List<Integer> ans = new ArrayList<Integer>();
Node cur = graph[farest];
while (cur.val != mid) {
for (int i : cur.adj) {
if (graph[i].val + 1 == cur.val) {
cur = graph[i];
break;
}
}
}
if (two) {
for (int i : cur.adj) {
if (graph[i].val + 1 == cur.val) {
cur = graph[i];
break;
}
}
}
return ans;

}
private int farest = 0;
private void DFS(Node[] graph, int start, int layer, boolean[] visited){
visited[start] = true;
graph[start].val = layer;
if(graph[farest].val < graph[start].val) farest = start;
if(!visited[i])
DFS(graph, i, layer+1, visited);
}
}
}``````

• long and uncommented.....

• you can figure it out yourself.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.