Find largest distance Given an arbitrary unweighted rooted tree which consists of N (2 <= N <= 40000) nodes. The goal of the problem is to find largest distance between two nodes in a tree. Distance between two nodes is a number of edges on a path between the nodes (there will be a unique path between any pair of nodes since it is a tree). The nodes will be numbered 0 through N - 1.
The tree is given as an array P, there is an edge between nodes P[i] and i (0 <= i < N). Exactly one of the i’s will have P[i] equal to -1, it will be root node.
Example: If given P is [-1, 0, 0, 0, 3], then node 0 is the root and the whole tree looks like this:
0
/ | \
1 2 3
\
4
One of the longest path is 1 -> 0 -> 3 -> 4 and its length is 3, thus the answer is 3. Note that there are other paths with maximal distance.
Solution:
public class Solution { public int solve(ArrayList<Integer> A) { int n = A.size(); Map<Integer, List<Integer>> edges = new HashMap<>(); int[] inDegrees = new int[n]; for (int i = 0; i < n; i ++) { int parent = A.get(i); int child = i; List<Integer> children = edges.getOrDefault(parent, new ArrayList<>()); children.add(child); edges.put(parent, children);
List<Integer> children2 = edges.getOrDefault(child, new ArrayList<>()); children2.add(parent); edges.put(child, children2);
if (parent != -1) { inDegrees[parent] ++; } } // System.out.println(Arrays.toString(inDegrees)); int[] max = new int[]{0}; for (int i = 0; i < n; i ++) { if (inDegrees[i] == 0) { boolean[] visited = new boolean[n]; dfs(0, edges, visited, 0, max); } } return max[0]; }
private void dfs(int i, Map<Integer, List<Integer>> edges, boolean[] visited, int pathLen, int[] max) { if (i == -1 || visited[i]) return; max[0] = Math.max(max[0], pathLen); visited[i] = true; if (edges.containsKey(i)) { for (int next : edges.get(i)) { dfs(next, edges, visited, pathLen + 1, max); } } } }
Solution2:
public class Solution { private int maxDist = 0;
public class Node { int val; int height; ArrayList<Node> children;
public Node(int val) { this.val = val; this.height = 0; children = new ArrayList<>(); } }
private Node constructGraph(Node[] nodes, ArrayList<Integer> A) { Node root = null; for (int i = 0; i < A.size(); i++) { if (nodes[i] == null) { nodes[i] = new Node(i); } int parent = A.get(i); if (parent == -1) { root = nodes[i]; } else { if (nodes[parent] == null) nodes[parent] = new Node(parent); nodes[parent].children.add(nodes[i]); } } return root; }
private void setHeights(Node root) { Stack<Node> stack1 = new Stack<>(); Stack<Node> stack2 = new Stack<>(); stack1.push(root); while (!stack1.isEmpty()) { Node node = stack1.pop(); if (node.children.size() != 0) { // not leaf! stack2.push(node); // push all non-leaf nodes to stack2 for processing later for (Node child: node.children) { stack1.push(child); } } } while (!stack2.isEmpty()) { Node node = stack2.pop(); for (Node child: node.children) { node.height = Math.max(node.height, child.height + 1); } } }
private void calculateMaxDist(Node root) { int maxDepth1 = 0; int maxDepth2 = 0; for (Node child: root.children) { int maxDepth = child.height + 1; if (maxDepth >= maxDepth1) { maxDepth2 = maxDepth1; maxDepth1 = maxDepth; } else if (maxDepth > maxDepth2) { maxDepth2 = maxDepth; } } maxDist = Math.max(maxDist, maxDepth1 + maxDepth2); }
public int solve(ArrayList<Integer> A) { Node[] nodes = new Node[A.size()]; Node root = constructGraph(nodes, A); setHeights(root); for (Node node: nodes) { calculateMaxDist(node); }
return maxDist; } }
Solution3:
first BFS to find leaf node that is the deepest, then do another bfs from that node to find the largest distance
public class Solution { private void bfs(int root, Map<Integer, List<Integer>> edges, int[] fur, int[] max) { int[] dist = new int[edges.size()]; Arrays.fill(dist, -1); dist[root] = 0; Deque<Integer> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int parent = queue.poll(); for (int child : edges.getOrDefault(parent, new ArrayList<>())) { if (dist[child] == -1) { queue.offer(child); dist[child] = dist[parent] + 1; } } } for (int i = 0; i < dist.length; i ++) { int d = dist[i]; if (d > max[0]) { max[0] = d; fur[0] = i; } } }
public int solve(ArrayList<Integer> A) { int n = A.size(); Map<Integer, List<Integer>> edges = new HashMap<>(); int root = -1; for (int i = 0; i < n; i ++) { int parent = A.get(i); int child = i; List<Integer> children = edges.getOrDefault(parent, new ArrayList<>()); children.add(child); edges.put(parent, children);
if (parent != -1) { List<Integer> children2 = edges.getOrDefault(child, new ArrayList<>()); children2.add(parent); edges.put(child, children2); }
if (parent == -1) { root = i; } } int[] fur = new int[]{0}; int[] max = new int[]{0}; bfs(root, edges, fur, max); bfs(fur[0], edges, fur, max); return max[0]; } }