The graph contains
n
nodes which are labeled from 0
to n - 1
. You will be given the number n
and a list of undirected edges
(each edge is a pair of labels).edges
. Since all edges are undirected, [0, 1]
is the same as [1, 0]
and thus will not appear together in edges
.n = 4
, edges = [[1, 0], [1, 2], [1, 3]]
0 | 1 / \ 2 3
[1]
n = 6
, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2 \ | / 3 | 4 | 5
[3, 4]
Longest Path
It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree.
Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).
Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs).
The following is some thought of the latter.
Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.
Then y must be one of the endpoints on some longest path.
Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.
Now, the path from y to z is the longest one, and thus its middle point(s) is the answer.
Tree DP
Alternatively, one can solve this problem directly by tree dp.
Let dp[i] be the height of the tree when the tree root is i.
We compute dp[0] ... dp[n - 1] by tree dp in a dfs manner.
Arbitrarily pick a node, say node 0, as the root, and do a dfs.
When we reach a node u, and let T be the subtree by removing all u's descendant (see the right figure below).
We maintain a variable acc that keeps track of the length of the longest path in T with one endpoint being u.
Then dp[u] = max(height[u], acc)
Note, acc is 0 for the root of the tree.
| |
. .
/|\ /|\
* u * * u *
/|\
/ | \
* v *
. denotes a single node, and * denotes a subtree (possibly empty).
Now it remains to calculate the new acc for any of u's child, v.
It is easy to see that the new acc is the max of the following
acc + 1 --- extend the previous path by edge uv;
max(height[v'] + 2), where v != v' --- see below for an example.
u /| / | v' v | . . . | .
In fact, the second case can be computed in O(1) time instead of spending a time proportional to the degree of u.
Otherwise, the runtime can be quadratic when the degree of some node is Omega(n).
The trick here is to maintain two heights of each node, the largest height (the conventional height), and the second largest height
(the height of the node after removing the branch w.r.t. the largest height).
Therefore, after the dfs, all dp[i]'s are computed, and the problem can be answered trivially.
The total runtime is still O(n). Java Solution
/*
*剥洋葱解法:从外层向里层进行BFS遍历
*具体思路:
*将图转化为邻接表存储后,若只有一条边的则为最外围的元素,将外围元素全部加入队列
*然后在队列弹出时,需要将这个结点在邻接表中删除,层层向里,最后只剩下2个元素以内时,则为最中心元素,即以它们作为树根会得到最小高度树
*/
这个在VS里是能通过的。 可是在LC中,(例如第一个例子) map第一遍的时候,就空了。而VS中还有一个值
class Solution { public: vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { // idea : peel the onion, until the valid unordered_map<int,unordered_set<int>> map; for (auto edge : edges) { int a = edge[0], b = edge[1]; map[a].insert(b); map[b].insert(a); } vector<int> res; while (true) { auto copy = map; auto iter = map.begin(); while (iter != map.end()) { if (iter->second.size() <= 1) { // must be <=1, as exist no edges int a = iter->first; if (iter->second.size() == 1) { auto anotherEnd = *(iter->second.begin()); map[anotherEnd].erase(a); } iter = map.erase(iter); } else { iter++; } } if (map.size() == 0) { // then nodes before this round, would be ansers iter = copy.begin(); while (iter != copy.end()) { res.push_back(iter->first); iter++; } break; } } return res; // shall not hit } };
Mistakes:
No comments:
Post a Comment