2458. Height of Binary Tree After Subtree Removal Queries Hard

1/**
2 * [2458] Height of Binary Tree After Subtree Removal Queries
3 *
4 * 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.
5 * You have to perform m independent queries on the tree where in the i^th query you do the following:
6 * 
7 * 	Remove the subtree rooted at the node with the value queries[i] from the tree. It is guaranteed that queries[i] will not be equal to the value of the root.
8 * 
9 * Return an array answer of size m where answer[i] is the height of the tree after performing the i^th query.
10 * Note:
11 * 
12 * 	The queries are independent, so the tree returns to its initial state after each query.
13 * 	The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.
14 * 
15 *  
16 * <strong class="example">Example 1:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png" style="width: 495px; height: 281px;" />
18 * Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
19 * Output: [2]
20 * Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
21 * The height of the tree is 2 (The path 1 -> 3 -> 2).
22 * 
23 * <strong class="example">Example 2:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png" style="width: 301px; height: 284px;" />
25 * Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
26 * Output: [3,2,3,2]
27 * Explanation: We have the following queries:
28 * - Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
29 * - Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
30 * - Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
31 * - Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	The number of nodes in the tree is n.
37 * 	2 <= n <= 10^5
38 * 	1 <= Node.val <= n
39 * 	All the values in the tree are unique.
40 * 	m == queries.length
41 * 	1 <= m <= min(n, 10^4)
42 * 	1 <= queries[i] <= n
43 * 	queries[i] != root.val
44 * 
45 */
46pub struct Solution {}
47use crate::util::tree::{TreeNode, to_tree};
48
49// problem: https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/
50// discuss: https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54// Definition for a binary tree node.
55// #[derive(Debug, PartialEq, Eq)]
56// pub struct TreeNode {
57//   pub val: i32,
58//   pub left: Option<Rc<RefCell<TreeNode>>>,
59//   pub right: Option<Rc<RefCell<TreeNode>>>,
60// }
61// 
62// impl TreeNode {
63//   #[inline]
64//   pub fn new(val: i32) -> Self {
65//     TreeNode {
66//       val,
67//       left: None,
68//       right: None
69//     }
70//   }
71// }
72use std::rc::Rc;
73use std::cell::RefCell;
74impl Solution {
75    pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {
76        vec![]
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_2458() {
88    }
89}
90