✅ Explained step by step easy to understand | 8 ms Beats 99.79% ✨
Intuition\nThe problem revolves around finding the height of subtrees after removing a specified node. Observing that the subtree height heavily depends on the 
# Intuition\nThe problem revolves around finding the height of subtrees after removing a specified node. Observing that the subtree height heavily depends on the tree\'s structure and levels, we can preprocess the tree to store the height of each node. This allows us to quickly compute the new height when a node is removed. Additionally, by maintaining the highest and second-highest subtree heights at each level, we can efficiently handle the height adjustments when a particular node is removed.\n\n![Screenshot 2024-10-27 002039.png](https://assets.leetcode.com/users/images/8982468a-d7fb-4d66-8b2f-2957e14e83bb_1729968658.0026693.png)\n\n\n# Approach\n1. **Preprocessing Heights:**\n    - We define arrays height, maxHt, and secondMaxHt to keep track of the height of each node and the two highest heights at each level of the tree.\n    - Using DFS, traverse the tree to calculate the height of each node and store it in the height array.\n2. **Track Maximum Heights:**\n    - While traversing, update maxHt and secondMaxHt at each level based on the node\'s height. This helps us quickly determine the new height of the tree if the current node is removed.\n\n3. **Query Processing:**\n    - For each query, get the level of the queried node.\n    - Calculate the new height by using either maxHt or secondMaxHt based on whether the queried node\'s height matches the maximum height at that level.\n\n4. **Return Results:**\n    - Update each query with the computed result and return the modified query list.\n\n# Complexity\n- Time complexity:O(N+Q)\n    - Where N is the number of nodes in the tree, as we traverse it once to compute heights.\n    - Q is the number of queries, each processed in constant time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n    - Due to the storage arrays for heights, levels, and max heights.\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    int level[100001];\n    int height[100001];\n    int maxHt[100001];\n    int secondMaxHt[100001];\n\n    int findHeight(TreeNode* root, int lvl)\n    {\n        if(root == NULL) return 0;\n\n        level[root->val] = lvl;\n        height[root->val] = max(findHeight(root->left, lvl+1), findHeight(root->right, lvl+1)) + 1;\n        if(maxHt[lvl] < height[root->val])\n        {\n            secondMaxHt[lvl] = maxHt[lvl];\n            maxHt[lvl] = height[root->val];\n        }\n        else if(secondMaxHt[lvl] < height[root->val])\n        {\n            secondMaxHt[lvl] = height[root->val];\n        }\n\n        return height[root->val];\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        findHeight(root, 0);\n        // vector<int> result;\n\n        for(int i=0; i<queries.size(); i++)\n        {\n            int temp = queries[i];\n            int L = level[temp];\n            int tempRes = L + (maxHt[L] == height[temp] ? secondMaxHt[L] : maxHt[L]) - 1;\n\n            queries[i] = tempRes;\n        }\n\n        return queries;\n    }\n};\n```\n``` java []\nclass Solution {\n    int[] level = new int[100001];\n    int[] height = new int[100001];\n    int[] maxHt = new int[100001];\n    int[] secondMaxHt = new int[100001];\n\n    public int findHeight(TreeNode root, int lvl) {\n        if (root == null) return 0;\n\n        level[root.val] = lvl;\n        height[root.val] = Math.max(findHeight(root.left, lvl + 1), findHeight(root.right, lvl + 1)) + 1;\n\n        if (maxHt[lvl] < height[root.val]) {\n            secondMaxHt[lvl] = maxHt[lvl];\n            maxHt[lvl] = height[root.val];\n        } else if (secondMaxHt[lvl] < height[root.val]) {\n            secondMaxHt[lvl] = height[root.val];\n        }\n\n        return height[root.val];\n    }\n\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        findHeight(root, 0);\n\n        for (int i = 0; i < queries.length; i++) {\n            int temp = queries[i];\n            int L = level[temp];\n            int tempRes = L + (maxHt[L] == height[temp] ? secondMaxHt[L] : maxHt[L]) - 1;\n\n            queries[i] = tempRes;\n        }\n\n        return queries;\n    }\n}\n```\n![a-comic-book-style-medium-shot-of-spider-man-with--hQ85udCLRDKHCvQgDaCiAA-FBBD11lsRcStr9_QxbkY7w.jpeg](https://assets.leetcode.com/users/images/dac087b3-db74-4f27-824a-e08c75ff7a99_1729968595.3307774.jpeg)\n
['Array', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java']