550. Height After Cutting
An orchard grower models a tree as a binary tree of branch IDs rooted at root. Its height is the number of parent-to-child links on the longest downward path from the root, so a tree that is a single branch has height 0. The grower plans queries.length independent trims. In the i-th trim, the branch whose ID is queries[i] is cut off together with everything growing from it.
Return an array answer of the same length as queries where answer[i] is the height of the orchard tree after performing only the i-th trim. After each trim the tree grows back to its original shape before the next one is considered.
Example 1
- Input:
- root = [10,4,16,2,7,12,20,1], queries = [2,1,4,16]
- Output:
- [2,2,2,3]
- Explanation:
Cutting 2, 1 or 4 removes the only branch of height 3, leaving height 2; cutting 16 leaves the left branch 10-4-2-1, so the height stays 3.
Example 2
- Input:
- root = [6,3], queries = [3]
- Output:
- [0]
- Explanation:
Cutting away the only child leaves just the root, whose height is 0.
Constraints
1 ≤ number of nodes ≤ 105
1 ≤ Node.val ≤ 105, all values distinct
1 ≤ queries.length ≤ 104
Each queries[i] is the value of a node in the tree, and it is not the value of the root.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n + q)
- Space
- O(n)