LeetCode 310: Minimum Height Trees
LeetCode 310 Solution Explanation
Explanation:
To find the minimum height trees (MHTs) in a given tree, we can use a two-step process:
- Trimming Leaves: We iteratively remove the leaf nodes (nodes with only one neighbor) from the tree until only 1 or 2 nodes are left.
- BFS from Leaves: Starting from the remaining nodes (1 or 2), we perform a Breadth First Search (BFS) to find the MHTs.
Algorithm:
- Create an adjacency list representing the tree.
- Initialize a queue with all leaf nodes.
- Remove the leaf nodes from the tree and update the degrees of their neighbors.
- Add new leaf nodes (nodes with updated degree = 1) to the queue.
- Repeat steps 3-4 until only 1 or 2 nodes are left.
- Perform BFS from the remaining nodes to find MHTs.
Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n), to store the adjacency list and queue.
:
LeetCode 310 Solutions in Java, C++, Python
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Collections.singletonList(0);
}
List<Set<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new HashSet<>());
}
int[] degree = new int[n];
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
adjList.get(edge[1]).add(edge[0]);
degree[edge[0]]++;
degree[edge[1]]++;
}
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
leaves.offer(i);
}
}
while (n > 2) {
int leavesSize = leaves.size();
n -= leavesSize;
for (int i = 0; i < leavesSize; i++) {
int leaf = leaves.poll();
for (int neighbor : adjList.get(leaf)) {
degree[neighbor]--;
if (degree[neighbor] == 1) {
leaves.offer(neighbor);
}
}
}
}
List<Integer> result = new ArrayList<>(leaves);
return result;
}
}Interactive Code Editor for LeetCode 310
Improve Your LeetCode 310 Solution
Use the editor below to refine the provided solution for LeetCode 310. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...