✅ [Python/C++/Java/Rust] code-as-explanation + BONUS (with detailed comments)
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs a Depth First Search approach to compute heights & depths of tree nodes. Time complex
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs a Depth First Search approach to compute heights & depths of tree nodes. Time complexity is linear: **O(m+n)**. Space complexity is linear: **O(m+n)**\n\n**Comment**. The strategy here is to pre-compute three maps:\n1. `depths` is a map that stores for each node its depth, i.e., the distance from the top (root) of the tree;\n2. `height` is a map that stores for each node its height, i.e., the maximal length of a path to the bottom of the tree that starts from this node;\n3. `levels` is a map that stores for each level (depth) a list of nodes on that level.\n\nThe idea of the solution is simple: when we remove a node, the maximal height of the resulting tree is the sum of:\n* the depth of removed node\'s parent (i.e., parent\'s level) and\n* the maximal height of the **remaining** nodes on the removed node\'s level.\n\n**Python** self-explanatory (and easy-to-read) code that realizes this strategy is presented below.\n```\nclass Solution:\n    \n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n    \n        height, depths, levels = {}, {}, defaultdict(list)\n        \n        def dfs(n, d):\n            if not n: return 0\n            h = 1 + max(dfs(n.left, d+1), dfs(n.right, d+1))\n            levels[d].append(n.val)\n            height[n.val] = h\n            depths[n.val] = d\n            return h\n        \n        @functools.cache\n        def query(q):\n            max_height = max([height[v] for v in levels[depths[q]] if v != q] or [0])\n            return depths[q] - 1 + max_height\n        \n        dfs(root, 0)     \n        \n        return [query(q) for q in queries]\n```\n\nAs a bonus, I provide a more concise solution in various languages. It turns out that we can precompute the result for each possible query right inside the DFS function by using memoization/cache of height.\n<iframe src="https://leetcode.com/playground/iwDQo4e9/shared" frameBorder="0" width="800" height="640"></iframe>
[]