Height of Binary Tree After Subtree Removal Queries
You are given the root of a binary tree with n nodes. Each node is assigned a unique value from 1 to n. You are also given an array queries of size m.
You have to perform m independent queries on the tree where in the i^th query you do the following:
- Remove the subtree rooted at the node with the value
queries[i]from the tree. It is guaranteed thatqueries[i]will not be equal to the value of the root.
Return an array answer of size m where answer[i] is the height of the tree after performing the i^th query.
Note:
- The queries are independent, so the tree returns to its initial state after each query.
- The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.
Example 1
1
/ \
3 4
/ / \
2 6 5
\
7Input
root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]Output
[2]After removing the subtree rooted at node 4, the remaining tree has height 2 via the path 1 -> 3 -> 2.
Example 2
5
/ \
8 9
/ \ / \
2 1 3 7
/ \
4 6Input
root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]Output
[3,2,3,2]The resulting heights after removing the subtrees rooted at 3, 2, 4, and 8 are 3, 2, 3, and 2 respectively.
Constraints
- The number of nodes in the tree is
n. - 2 <= n <= 10^5
- 1 <= Node.val <= n
- All the values in the tree are unique.
- m == queries.length
- 1 <= m <= min(n, 10^4)
- 1 <= queries[i] <= n
- queries[i] != root.val