Python | DFS & Precomputation
see the Successfully Accepted Submission\n\n# Code\npython3 []\nfrom typing import List, Optional\n\n# Definition for a binary tree node.\nclass TreeNode:\n    
[see the Successfully Accepted Submission](https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/submissions/1433872401/?envType=daily-question&envId=2024-10-26)\n\n# Code\n```python3 []\nfrom typing import List, Optional\n\n# Definition for a binary tree node.\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        depths = {}\n        heights = {}\n        \n        # Step 1: Compute heights and depths using DFS\n        def compute_heights(node, depth):\n            if not node:\n                return -1\n            depths[node.val] = depth\n            left_height = compute_heights(node.left, depth + 1)\n            right_height = compute_heights(node.right, depth + 1)\n            heights[node.val] = 1 + max(left_height, right_height)\n            return heights[node.val]\n        \n        compute_heights(root, 0)\n        \n        # Step 2: Precompute the maximum heights for each level excluding subtrees\n        max_height_without_subtree = {}\n        level_max_height = {}\n        \n        # Collect the max heights for each depth level\n        def update_level_heights(node):\n            if not node:\n                return\n            depth = depths[node.val]\n            if depth not in level_max_height:\n                level_max_height[depth] = []\n            level_max_height[depth].append(heights[node.val])\n            update_level_heights(node.left)\n            update_level_heights(node.right)\n        \n        update_level_heights(root)\n        \n        # Sort each level\'s heights in descending order to allow easy access to the top two heights\n        for depth in level_max_height:\n            level_max_height[depth].sort(reverse=True)\n        \n        # Compute maximum height of the tree excluding each node\'s subtree\n        for node_val in heights:\n            depth = depths[node_val]\n            max_heights = level_max_height[depth]\n            \n            # Determine the max height excluding the subtree at this node\n            if len(max_heights) == 1:\n                max_height_without_subtree[node_val] = depth - 1\n            elif heights[node_val] == max_heights[0]:\n                max_height_without_subtree[node_val] = depth + (max_heights[1] if len(max_heights) > 1 else 0)\n            else:\n                max_height_without_subtree[node_val] = depth + max_heights[0]\n        \n        # Step 3: Answer each query\n        return [max_height_without_subtree[q] for q in queries]\n\n```\n\n# Step-by-Step Explanation\n\n## Step 1: Compute Heights and Depths of Each Node\n\n### Depth-First Search (DFS) Traversal\nThe `compute_heights` function traverses the tree using DFS to compute the depth and height of each node.\n\n### Depth Storage\n- The `depths` dictionary stores each node\'s depth, where `depths[node.val] = depth`.\n- The `depth` variable tracks the current depth level during traversal, starting from `0` at the root.\n\n### Height Calculation\n- The `heights` dictionary stores the height of each node, where `heights[node.val]` is the maximum depth reachable from that node.\n- Each node\u2019s height is calculated as `1 + max(left_height, right_height)`, where `left_height` and `right_height` are the heights of the left and right subtrees, respectively.\n- If a node is `None` (a leaf node), it returns `-1`, making leaf nodes have a height of `0`.\n\n## Step 2: Precompute Maximum Heights for Each Level Excluding Subtrees\n\n### Collecting Heights by Level\n- The `update_level_heights` function collects heights for each depth level in the dictionary `level_max_height`.\n- For each node, it appends its height to the list associated with its depth level (`level_max_height[depth]`).\n- This function performs a full tree traversal to ensure that every node\u2019s height is collected.\n\n### Sorting Heights\n- After collecting heights for each depth, the algorithm sorts each depth level\u2019s list in descending order (`level_max_height[depth].sort(reverse=True)`).\n- Sorting allows easy access to the two highest subtree heights for each depth level.\n\n### Calculating Maximum Heights Excluding Each Node\u2019s Subtree\n- For each node, the algorithm calculates the maximum height of the tree if the node\u2019s subtree were excluded, storing these values in `max_height_without_subtree`.\n- To determine the maximum height without a specific node\u2019s subtree, two cases are considered:\n  - If the node\u2019s height is the highest in its depth level, the next highest height at that level is used.\n  - If the node\u2019s height is not the highest, the highest height at that level is used.\n- This allows us to "exclude" the subtree rooted at a particular node by selecting the next tallest subtree.\n\n## Step 3: Answer Queries\n- Finally, for each query in `queries`, the algorithm retrieves the precomputed height from `max_height_without_subtree`.\n- This is done in constant time for each query since the dictionary `max_height_without_subtree` already holds the values needed.\n\n## Complexity Analysis\n\n### Time Complexity\nThe algorithm performs two full traversals of the tree, resulting in \\( O(N) \\) complexity for tree traversal steps. Sorting the heights lists takes \\( O(D \\log D) \\) where \\( D \\) is the depth, but this is typically less significant than the traversal for most balanced trees.\n\n### Space Complexity\nThe space complexity is \\( O(N) \\) due to the storage in `depths`, `heights`, `level_max_height`, and `max_height_without_subtree`.\n\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']