Minimum Height Trees
Problem
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of
n
nodes labelled from0
ton - 1
, and an array ofn - 1
edges
whereedges[i] = [ai, bi]
indicates that there is an undirected edge between the two nodesai
andbi
in the tree, you can choose any node of the tree as the root. When you select a nodex
as the root, the result tree has heighth
. Among all possible rooted trees, those with minimum height (i.e.min(h)
) are called minimum height trees (MHTs).Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]
Pseudocode
- topo approach, trime all the leaves to find the core nodes
- need to review this solution
Solution
// from solutions
// https://leetcode.com/problems/minimum-height-trees/solutions/427802/javascript-bfs-solution/
var findMinHeightTrees = function (n, edges) {
if (!edges || n < 2) return [0];
let graph = [];
// parse edges
for (let [x, y] of edges) {
graph[x] = graph[x] || [];
graph[y] = graph[y] || [];
graph[x].push(y);
graph[y].push(x);
}
let leaves = [];
// init leaf nodes
graph.map((pts, i) => pts.length === 1 && leaves.push(i));
while (n > 2) {
n = n - leaves.length;
let nxt_leaves = [];
for (let leave of leaves) {
// remove leaf node and itself in related nodes
tmp = graph[leave].pop();
graph[tmp].splice(graph[tmp].indexOf(leave), 1);
// save new leaf node
graph[tmp].length === 1 && nxt_leaves.push(tmp);
}
leaves = nxt_leaves;
}
return leaves;
};
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated