2458. Height of Binary Tree After Subtree Removal Queries
Explanation:
To solve this problem, we can perform depth-first search (DFS) to traverse the tree and remove the subtree rooted at a specific node as requested in each query. We can maintain the heights of the tree after each query and return them in the final answer array.
- We first create a map to store the parent-child relationships for each node in the tree.
- We then perform a DFS traversal to build the parent-child relationships and calculate the height of each node.
- For each query, we remove the subtree rooted at the queried node and update the heights of the affected nodes.
- We return the heights of the tree after each query.
Time Complexity: O(n + m) where n is the number of nodes in the tree and m is the number of queries. Space Complexity: O(n) for maintaining the parent-child relationships and heights.
:
class Solution {
Map<Integer, List<Integer>> graph = new HashMap<>();
int[] heights;
public int[] heightHelper(TreeNode node) {
if (node == null) return new int[0];
int left = 0, right = 0;
if (node.left != null) {
int[] l = heightHelper(node.left);
left = 1 + Math.max(l[0], l[1]);
}
if (node.right != null) {
int[] r = heightHelper(node.right);
right = 1 + Math.max(r[0], r[1]);
}
heights[node.val] = Math.max(left, right);
return new int[]{left, right};
}
public int[] removeSubtreesAndReturnHeights(TreeNode node, int[] queries) {
for (int q : queries) graph.put(q, new ArrayList<>());
heightHelper(node);
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int query = queries[i];
for (int child : graph.get(query)) {
heights[child] = 0;
}
result[i] = heights[node.val];
}
return result;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement 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.