I have trained my algorithm on leetcode a period of time.

Today, I will explain my solution about Minimum Height Trees. My solution beat ~95% against others but it is hard to explain what is I do. Please allow me to introduce the solution from easy to hard. If you only need the last solution, jump to Solution 4.

List of Solutions:

### Brute Force Solution

Brute force solution is very easy and direct. Enumerate every node of tree, find the longest path depends on problem description with DFS.

### Cut Leaves Solution

Cut leaves of current tree, repeat this process until there are one or two leaves left.

### Find Diameter Solution

Use two DFS to find the diameter and record the diameter path, then pick the middle node what answer is.

### DP-DFS Solution

a[i] convert edges to adjacency list of i

ret[i] the LPL when i as root, so finally we find all smallest ret, that is the answer.

d0[i] the LPL begin with node i through one child of i.

d1[i] the second path length begin with node i through another child of i, if i only have one child, then d1[i] == 0

up_path[i] the path go up through father of i reach one leaf

So, I calculate the d0 and d1 in calc_d, we just travel the tree and get every path length which through child, and assign longest to d0 and second longest to d1

Well, we do many work for this moment, we almost meet our truth.

If we have d0[cur], up_path[cur] as above, the ret[cur] = max(d0[cur], up_path[cur]), is very simple, right? In dfs we will figure out up_path(it will figure out in-place so we don’t need array) and ret[cur]. If the path of d0[cur] is in the path of d0[fa](that says they both coincide most partly), up_path will be max(d1[fa], fa_up_path)+1(must compare the other path of father instead of this path contains cur), otherwise, will be max(d0[fa], fa_up_path)+1. Then travel every child do the same thing.

This solution will save tons of time because it don’t calculate repeatedly any path twice. DRY. :)

Actually, I wrote four solutions from fastest to slowest. The order of solutions is tree-dp which I explain above, use dfs twice to find the diameter of a tree and record the path, then find the center. The third is cutting the leaves again and again until only one or two node. The lastest is just enumerating every node to find the longest path, then pick the shortest path.