LeetCode 1245: Tree Diameter
Problem Description
Explanation
To find the diameter of a tree, we need to find the longest path between any two nodes in the tree. We can solve this problem using Depth-First Search (DFS). The idea is to perform two DFS traversals. First, we start from an arbitrary node and find the farthest node from it. Then, we start from that farthest node and find the farthest node from it. The distance between these two farthest nodes will be the diameter of the tree.
- Perform a DFS traversal starting from an arbitrary node to find the farthest node (let's call it
node1) from it. - Perform another DFS traversal starting from
node1to find the farthest node (let's call itnode2) from it. - The distance between
node1andnode2will be the diameter of the tree.
Time complexity: O(N) - We visit each node once during the two DFS traversals. Space complexity: O(N) - We use recursive stack space for DFS.
Solutions
class Solution {
public int treeDiameter(int[][] edges) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
int[] farthest = findFarthestNode(graph, 0);
farthest = findFarthestNode(graph, farthest[0]);
return farthest[1];
}
private int[] findFarthestNode(Map<Integer, List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
int[] farthest = new int[] {start, 0};
dfs(graph, visited, start, 0, farthest);
return farthest;
}
private void dfs(Map<Integer, List<Integer>> graph, boolean[] visited, int node, int distance, int[] farthest) {
visited[node] = true;
if (distance > farthest[1]) {
farthest[0] = node;
farthest[1] = distance;
}
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited[neighbor]) {
dfs(graph, visited, neighbor, distance + 1, farthest);
}
}
}
}Loading editor...