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.
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.
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.
Hi, this is More Freeze. I am a backend engineer / video game player (specially ACT, PUZ) / board gamer in Beijing. I am good at C++, PHP, Python deveploping.
You can contact me via: