Well-explained || C++ || Height+Level ||O(N)
Intuition\nWhat we need to think is that in what cases will the height of the overall tree be affected by deleting the given node.This leads us to realizing tha
# Intuition\nWhat we need to think is that in what cases will the height of the overall tree be affected by deleting the given node.This leads us to realizing that it depends on the heights of the other nodes at the same level as the given node.It\'ll become clearer when you see the code\n\n# Approach\nThe code uses a recursive function, height, to traverse the binary tree and calculate the height of each node.\nIt maintains two vectors, levels and lev, to store information about the levels and heights of the nodes.\nThe levels vector is a 2D vector, where each row represents a level in the tree. Each row consists of two pairs: the first pair stores the maximum height and its corresponding node value, and the second pair stores the second maximum height and its corresponding node value.\nThe lev vector is used to store the level of each node.\nThe height function recursively calculates the height of each node and updates the levels and lev vectors accordingly.\nOnce the height function has traversed the entire tree, the code processes the queries.\nFor each query, it retrieves the level and node value.\nIf the queried node is the left child of its parent (i.e., it is stored in the first pair of the levels vector for its level), the code calculates the height of the node from the root using the heights stored in the first and second pairs of the levels vector.\nIf the queried node is the right child of its parent (i.e., it is stored in the second pair of the levels vector for its level), the code simply calculates the height of the node from the root as ht - 1, where ht represents the overall height of the tree.\nThe calculated heights are stored in the ans vector, which is then returned as the result.\n\n# Complexity\n- Time complexity:O(N+Q)   \nLet\'s analyze the main operations:\nTraversing the binary tree to calculate heights: This process has a time complexity of O(N), where N is the number of nodes in the tree.\nProcessing queries: The code iterates through the queries, and for each query, it performs a constant number of operations. Therefore, the time complexity for processing queries is O(Q), where Q is the number of queries.\nOverall, the time complexity of the solution is O(N + Q), considering the traversal and query processing steps.\n\n- Space complexity:\nO(N+Q)\n\n# Code\n```\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    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        vector<vector<pair<int,int>>> levels(1e5,vector<pair<int,int>>(2,{0,0}));\n        vector<int> lev(1e5+1,0);\n        int ht=height(root,0,levels,lev);\n        vector<int> ans;\n        for(int i=0;i<queries.size();i++)\n        {\n            int node=queries[i];\n            int level=lev[node];\n            if(levels[level][0].second==node)\n            {\n                ans.push_back(ht-levels[level][0].first+levels[level][1].first-1);\n            }\n            else\n            {\n                ans.push_back(ht-1);\n            }\n        }\n        return ans;\n        \n    }\n    int height(TreeNode* root,int level,vector<vector<pair<int,int>>> &levels,vector<int> &lev)\n    {\n        if(root==NULL)\n            return 0;\n        lev[root->val]=level;\n        int hleft=height(root->left,level+1,levels,lev);\n        int hright=height(root->right,level+1,levels,lev);\n        int tmp=1+max(hleft,hright);\n        if(tmp>levels[level][0].first)\n           {\n            levels[level][1]=levels[level][0];\n            levels[level][0]={tmp,root->val};\n           }\n        else if(tmp>levels[level][1].first)\n            levels[level][1]={tmp,root->val};\n        return 1+max(hleft,hright);\n    }\n};\n```
['Binary Tree', 'C++']