Description
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 from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. 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.
Examples:
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]Solution in Python
Python
from collections import defaultdict, deque
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# Base case: if there's only one node, it is the root and the only MHT
if n == 1:
return [0]
# Create an adjacency list to represent the tree graph
adj = defaultdict(set)
# Build the adjacency list from the edges
for a, b in edges:
adj[a].add(b)
adj[b].add(a)
# Initialize a deque with all leaf nodes (nodes with only one connection)
leaves = deque([i for i in range(n) if len(adj[i]) == 1])
# The idea is to trim leaves layer by layer until 1 or 2 nodes remain
# These nodes will be the roots of MHTs
while n > 2:
# Number of leaves to be processed
leaves_size = len(leaves)
n -= leaves_size # Update remaining nodes count
# Process each leaf
for _ in range(leaves_size):
leaf = leaves.popleft() # Take one leaf from the deque
# The leaf node is connected to one neighbor
neighbor = adj[leaf].pop() # Remove the leaf from its neighbor's list
adj[neighbor].remove(leaf) # Remove the leaf from neighbor's connections
# If after removing the leaf, the neighbor becomes a leaf (only one connection), add it to the deque
if len(adj[neighbor]) == 1:
leaves.append(neighbor)
# After the process, the remaining nodes in 'leaves' are the roots of MHTs
return list(leaves)Detailed Explanation:
- Base Case: If there is only one node (
n = 1), that single node is the root of the tree and the only MHT. Hence, we return[0]. - Adjacency List Creation:
- We represent the tree using an adjacency list.
- For each edge
[a, b], we addbto the set of neighbors foraand vice versa.
- Identifying Leaves:
- A leaf is defined as a node that has only one connection.
- We identify all leaf nodes and store them in a deque (
leaves).
- Trimming Leaves:
- We iteratively remove leaves layer by layer, reducing the size of the tree.
- After removing a leaf, its connected neighbor might become a leaf if it now has only one remaining connection.
- This process continues until only 1 or 2 nodes remain.
- Result:
- The remaining nodes are the roots of the Minimum Height Trees (MHTs). These nodes will give the minimum height when used as the root of the tree.
Solution in C++
C++
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
// Base case: if there's only one node, it's the root of the only MHT
if (n == 1) {
return {0};
}
// Step 1: Create an adjacency list to represent the tree
vector<unordered_set<int>> adj(n);
// Step 2: Build the adjacency list from the edges
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].insert(v);
adj[v].insert(u);
}
// Step 3: Find all leaf nodes (nodes with only one connection)
queue<int> leaves;
for (int i = 0; i < n; ++i) {
if (adj[i].size() == 1) {
leaves.push(i); // This node is a leaf
}
}
// Step 4: Trim the leaves layer by layer until 1 or 2 nodes remain
while (n > 2) {
int leavesSize = leaves.size();
n -= leavesSize; // Reduce the number of remaining nodes
// Process each leaf
for (int i = 0; i < leavesSize; ++i) {
int leaf = leaves.front();
leaves.pop();
// The leaf node has only one neighbor
int neighbor = *adj[leaf].begin();
adj[neighbor].erase(leaf); // Remove the leaf from its neighbor
// If the neighbor becomes a leaf, add it to the queue
if (adj[neighbor].size() == 1) {
leaves.push(neighbor);
}
}
}
// Step 5: The remaining nodes in the queue are the roots of MHTs
vector<int> result;
while (!leaves.empty()) {
result.push_back(leaves.front());
leaves.pop();
}
return result;
}
};Solution in Javascript
JavaScript
var findMinHeightTrees = function(n, edges) {
// Base case: if there's only one node, it's the root of the only MHT
if (n === 1) {
return [0];
}
// Step 1: Create an adjacency list to represent the tree
const adj = Array.from({ length: n }, () => new Set());
// Step 2: Build the adjacency list from the edges
for (const [u, v] of edges) {
adj[u].add(v);
adj[v].add(u);
}
// Step 3: Find all leaf nodes (nodes with only one connection)
const leaves = [];
for (let i = 0; i < n; i++) {
if (adj[i].size === 1) {
leaves.push(i); // This node is a leaf
}
}
// Step 4: Trim the leaves layer by layer until 1 or 2 nodes remain
while (n > 2) {
const leavesSize = leaves.length;
n -= leavesSize; // Reduce the number of remaining nodes
// Process each leaf
for (let i = 0; i < leavesSize; i++) {
const leaf = leaves.shift(); // Remove the first leaf from the array
// The leaf node has only one neighbor
const neighbor = Array.from(adj[leaf])[0];
adj[neighbor].delete(leaf); // Remove the leaf from its neighbor
// If the neighbor becomes a leaf, add it to the leaves array
if (adj[neighbor].size === 1) {
leaves.push(neighbor);
}
}
}
// Step 5: The remaining nodes in the leaves array are the roots of MHTs
return leaves;
};Solution in Java
Java
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// Base case: if there's only one node, it is the root of the only MHT
if (n == 1) {
List<Integer> result = new ArrayList<>();
result.add(0);
return result;
}
// Step 1: Create an adjacency list to represent the tree
HashMap<Integer, HashSet<Integer>> adj = new HashMap<>();
for (int i = 0; i < n; i++) {
adj.put(i, new HashSet<>());
}
// Step 2: Build the adjacency list from the edges
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
// Step 3: Find all leaf nodes (nodes with only one connection)
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (adj.get(i).size() == 1) {
leaves.offer(i); // This node is a leaf
}
}
// Step 4: Trim the leaves layer by layer until 1 or 2 nodes remain
while (n > 2) {
int leavesSize = leaves.size();
n -= leavesSize; // Reduce the number of remaining nodes
// Process each leaf
for (int i = 0; i < leavesSize; i++) {
int leaf = leaves.poll(); // Remove the first leaf from the queue
// The leaf node has only one neighbor
int neighbor = adj.get(leaf).iterator().next(); // Get the only neighbor
adj.get(neighbor).remove(leaf); // Remove the leaf from its neighbor
// If the neighbor becomes a leaf, add it to the queue
if (adj.get(neighbor).size() == 1) {
leaves.offer(neighbor);
}
}
}
// Step 5: The remaining nodes in the queue are the roots of MHTs
List<Integer> result = new ArrayList<>();
while (!leaves.isEmpty()) {
result.add(leaves.poll());
}
return result;
}
}