Single traversal | Level-Order | CPP
Traverse the tree and compute the height of each node, level of each node and in each level store the max 2 heights.\nIf you remove a node, we have two possibil
Traverse the tree and compute the height of each node, level of each node and in each level store the max 2 heights.\nIf you remove a node, we have two possibilities. \n1. It\'s in the longest path\n2. It\'s not in the longest path\n\n```\nclass Solution {\n    unordered_map<int, int> nodeLevel;\n    unordered_map<int, pair<int,int>> heights;\n    unordered_map<int,int> height;\npublic:\n    int getHeight(TreeNode* root, int level) {\n        if (root == nullptr) return 0;\n        int lh = getHeight(root->left, level + 1);\n        int rh = getHeight(root->right, level + 1);\n        int h = 1 + max(lh, rh);\n        \n        nodeLevel[root->val] = level;\n        height[root->val] = h;\n        \n        if (heights.count(level)) {\n            if (heights[level].first <= h) {\n                pair<int,int> p = {h, heights[level].first};\n                heights[level] = p;\n            } else if (heights[level].second < h) {\n                heights[level].second = h;\n            }\n        } else {\n            heights[level] = {h, 0};\n        }\n        return h;\n    }\n    \n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        getHeight(root, 0);\n        vector<int> result;\n        for (auto node: queries) {\n            int level = nodeLevel[node];\n            if (height[node] == heights[level].first) {\n                result.push_back(heights[level].second + level - 1);\n            } else {\n                result.push_back(heights[level].first + level - 1);\n            }\n        }\n        return result;\n    }\n};\n```
['C++']