[With Drawing] C++ Single DFS, Record Each Level's Nodes
Intuition\n- depth is how many levels are beneath this node. Height is how many levels are above.\n- First, use DFS to find each node\'s{height, depth} and reco
# Intuition\n- `depth` is how many levels are beneath this node. `Height` is how many levels are above.\n- First, use DFS to find each node\'s`{height, depth}` and record in a map `mp`.\n- Second, loop through `mp`, and for each node, we add it to the corresponding height level. The map `nei[height]` records the nodes / neighbors with the same height. \n    - For example, `nei[2]` has the nodes `[2, 1, 3, 7]`:\n\n![IMG_2567A12487B6-1.jpeg](https://assets.leetcode.com/users/images/4ea95d57-0744-42af-b250-9ded99a549bf_1688256211.6916397.jpeg)\n\n- Each of the nodes has a depth, which are inserted in the `nei[2]`.\n- Finally, to remove `node 2`, we index into the corresponding height level and pop `node 2` in that level. So, nodes `[1, 3, 7]` remains. Among them, the max depth is `0`. So the result is `height + remaining max depth`.  \n- For optimization, we only keep the top two depth for each `nei` height level. Then, when sorting each level, we only sort two elements.\n\n# Complexity\n- Time complexity: $O(n)$\n\n- Space complexity: $O(n)$\n\n# Code C++\n```\nclass Solution {\npublic:\n    unordered_map<int, pair<int,int>> mp; // {height, depth}\n    int depth(TreeNode* cur, int cur_h){\n        if(cur == NULL){\n            return -1;\n        }\n        int left = depth(cur->left, cur_h + 1);\n        int right = depth(cur->right, cur_h + 1);\n        int cur_d = max(left, right) + 1;\n        mp[cur->val] = {cur_h, cur_d};\n        // cout << "Mp " << cur->val << ", h " << cur_h << ", d " << cur_d << endl;\n        return cur_d;\n    }\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        depth(root, 0);\n        unordered_map<int, vector<int>> nei;\n\n        for(auto& [key, val] : mp){\n            int h = val.first;\n            int d = val.second;\n            nei[h].push_back(d);\n            sort(nei[h].begin(), nei[h].end(), greater<int>());\n            if(nei[h].size() > 2){\n                nei[h].pop_back();\n            }\n        }\n\n\n        vector<int> res(queries.size());\n        for(int i = 0; i < queries.size(); i++){\n            int h = mp[queries[i]].first;\n            int d = mp[queries[i]].second;\n            if(nei[h].size() == 1){\n                res[i] = h - 1;\n            }else{\n                if(nei[h][0] == d){\n                    res[i] = h + nei[h][1];\n                }else{\n                    res[i] = h + nei[h][0];\n                }\n            }\n        }\n\n        return res;\n        \n    }\n};\n```
['C++']