LeetCode 3331: Find Subtree Sizes After Changes
Problem Description
Explanation
To solve this problem, we can perform a post-order traversal of the tree. For each node x, we recursively find the subtree size rooted at x and update the parent of x according to the rules mentioned in the problem. We can maintain a map to store the subtree sizes of each node. When updating the parent of a node x, we merge the subtree sizes of x with the subtree sizes of its new parent y.
Algorithm:
- Perform a post-order traversal of the tree.
- For each node x:
- Recursively find the subtree size rooted at x.
- Identify the closest ancestor y such that s[x] == s[y].
- If y exists, update the parent of x to y and merge the subtree sizes of x with y.
- Return the array of subtree sizes.
Time Complexity:
The time complexity of this algorithm is O(n) where n is the number of nodes in the tree.
Space Complexity:
The space complexity is O(n) for the array and map used to store the subtree sizes.
Solutions
class Solution {
public int[] countSubTrees(int n, int[] parent, String s) {
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 0; i < n; i++) {
tree.put(i, new ArrayList<>());
}
for (int i = 1; i < n; i++) {
tree.get(parent[i]).add(i);
}
Map<Integer, Integer> subtreeSizes = new HashMap<>();
postOrder(0, tree, parent, s, subtreeSizes);
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = subtreeSizes.get(i);
}
return result;
}
private int postOrder(int node, Map<Integer, List<Integer>> tree, int[] parent, String s, Map<Integer, Integer> subtreeSizes) {
int size = 1;
for (int child : tree.get(node)) {
size += postOrder(child, tree, parent, s, subtreeSizes);
}
int val = 1;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(node)) {
val += subtreeSizes.getOrDefault(i, 0);
}
}
subtreeSizes.put(node, val);
return size;
}
}Loading editor...