Problem Description
Explanation:
To solve this problem, we can follow these steps:
- Build a graph using the pairs where each node represents a unique value in the pairs array.
- Determine the root of the tree by finding the node with no incoming edges.
- Perform a topological sort to ensure that the tree structure is valid.
- Check if the tree can be uniquely reconstructed based on the given pairs.
If the tree can be uniquely reconstructed, there will be only one valid rooted tree. If there are multiple valid rooted trees possible, then there will be more than one way to reconstruct the tree. If there is no valid rooted tree possible, then return 0.
Time complexity: O(NlogN) where N is the number of pairs Space complexity: O(N)
: :
Solutions
class Solution {
public int checkWays(int[][] pairs) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for (int[] pair : pairs) {
graph.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);
graph.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);
indegree.put(pair[0], indegree.getOrDefault(pair[0], 0) + 1);
indegree.put(pair[1], indegree.getOrDefault(pair[1], 0) + 1);
}
int root = -1;
for (int node : indegree.keySet()) {
if (indegree.get(node) == pairs.length - 1) {
if (root == -1) {
root = node;
} else {
return 2;
}
}
}
if (root == -1) return 0;
int[] children = new int[2];
for (int child : graph.get(root)) {
children[indegree.get(child) > 1 ? 1 : 0] = child;
}
return isUnique(root, children, graph) ? 1 : 2;
}
private boolean isUnique(int root, int[] children, Map<Integer, Set<Integer>> graph) {
for (int child : children) {
Set<Integer> set = new HashSet<>(graph.get(child));
set.retainAll(graph.get(root));
if (set.size() > 1 || (set.size() == 1 && !isUnique(child, new int[]{set.iterator().next(), root}, graph))) {
return false;
}
}
return true;
}
}Loading editor...