Efficiently Calculating Tree Heights with Node Exclusions in a Binary Tree
Intuition\nThe task involves calculating the height of subtrees in a binary tree and determining the height of the tree if certain nodes are excluded. The idea 
# Intuition\nThe task involves calculating the height of subtrees in a binary tree and determining the height of the tree if certain nodes are excluded. The idea is to calculate the height of each subtree rooted at each node first, then find a way to compute the height of the tree if specific nodes are omitted. This approach allows us to answer queries efficiently.\n\n# Approach\n1. Calculate Subtree Heights: Use a recursive function to calculate the height of each subtree, storing results in each_subtree_height.\n\n2. Calculate Height Excluding Nodes: Traverse each level and, for each node, use the subtree height data to determine the height of the tree when this node is excluded. Store results in height_excluding_node.\n\n3. Answer Queries: For each query, use height_excluding_node to get the tree height when a specified node is excluded.\n\n# Complexity\n- ***Time complexity: O(n log n + m)***\n\n1. Calculating subtree heights: O(n).\n2. Calculating height excluding nodes: O(n log n) (due to the use of a priority queue for each level)\n3. Answering queries: O(m) m, where is the number of queries\n\n- **Space complexity: O(n)** for storing heights and intermediate results.\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 */\n\n// This solution efficiently handles each query by precomputing and storing relevant heights, making each query \uD835\uDC42(1) to access. \n\nclass Solution {\npublic:\n    int calculate_each_subtrees_height(TreeNode* root, unordered_map<TreeNode*, int> &each_subtree_height){\n        if(root == nullptr){\n            return 0;\n        }\n\n        int left_subtree_height = calculate_each_subtrees_height(root->left, each_subtree_height);\n        int right_subtree_height = calculate_each_subtrees_height(root->right, each_subtree_height);\n\n        each_subtree_height[root] = 1 + max(left_subtree_height, right_subtree_height);\n\n        return each_subtree_height[root];\n    }\n\n    void calculate_height_exclu_node( TreeNode* root, unordered_map<TreeNode*, int> each_subtree_height, unordered_map<int, int> &height_excluding_node){\n        queue<TreeNode*> q;\n        q.push(root);\n\n        int height = 0;\n\n        while(!q.empty()){\n            int n = q.size();\n            \n            priority_queue<pair<int, int>> pq;\n            for(int i=0; i<n; i++){\n                TreeNode* node = q.front();\n                q.pop();\n\n                pq.push({each_subtree_height[node], node->val});\n                if(node->left){\n                    q.push(node->left);\n                }\n\n                if(node->right){\n                    q.push(node->right);\n                }\n            }\n\n            pair<int, int> ele = pq.top();\n            pq.pop();\n\n            height_excluding_node[ele.second] = height + (pq.empty() ? 0 : pq.top().first);\n\n            while(!pq.empty()){\n                int a = pq.top().second;\n                height_excluding_node[a] = height + ele.first;\n                pq.pop();\n            }\n\n            height++;\n\n        }\n\n\n        return;\n\n    }\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        \n        unordered_map<TreeNode*, int> each_subtree_height;\n\n        calculate_each_subtrees_height(root, each_subtree_height);\n\n        unordered_map<int, int> height_excluding_node;\n\n        calculate_height_exclu_node(root, each_subtree_height, height_excluding_node);\n\n\n        int m = queries.size();\n        vector<int> ans(m, 0);\n\n        for(int i=0; i<m; i++){\n            ans[i] = height_excluding_node[queries[i]] - 1;\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Breadth-First Search', 'Heap (Priority Queue)', 'Binary Tree', 'C++']