Runtime beats 93.33%, memory 54.51 MB Beats 82.82% [w/ comments and explained]
Intuition\nWe want to know how the tree\u2019s shape changes if we \u201Cremove\u201D certain nodes. For each node, we find the height of its subtree (how far i
# Intuition\nWe want to know how the tree\u2019s shape changes if we \u201Cremove\u201D certain nodes. For each node, we find the height of its subtree (how far it goes down) and also keep track of the new \u201Cmax height\u201D of the entire tree if that node disappears, adjusting to account for whichever child subtree would remain.\n\n# Approach\nTraverse the tree to calculate and store heights for each node\u2019s subtree, then perform a depth-first traversal to find the \u201Cnew height\u201D of the tree for each node as if it were removed by updating heights using the remaining child subtrees, and finally retrieve the \u201Cnew height\u201D for each node in the query list.\n\n# Complexity\n- Time complexity:\nO(n) \u2014 where n is the number of nodes \u2014 since we visit each node a few times for height and depth-first calculations.\n\n- Space complexity:\nO(n) due to storing subtree heights and \u201Cnew heights\u201D for each node in arrays.\n\n# Code\n```python3 []\nfrom typing import List, Optional\n\nclass TreeNode:\n    # Definition for a binary tree node\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    # Define a large enough constant N to cover possible node values\n    N = 100001\n\n    def __init__(self):\n        # Initialize height and removal arrays\n        # val2H stores height of each node, initialized to -1\n        # removal stores the maximum depth if that node were removed, initialized to -1\n        self.val2H = [-1] * self.N\n        self.removal = [-1] * self.N\n\n    def h(self, root: Optional[TreeNode]) -> int:\n        # Calculate the height of the node\'s subtree rooted at \'root\'\n        if not root:\n            return -1  # Return -1 if root is None (no height for empty nodes)\n        x = root.val  # Get the value of the current node\n\n        # Return the cached height if already calculated\n        if self.val2H[x] != -1:\n            return self.val2H[x]\n        \n        # Recursively calculate the height as 1 + max height of left and right children\n        self.val2H[x] = 1 + max(self.h(root.left), self.h(root.right))\n        return self.val2H[x]\n\n    def dfs(self, root: Optional[TreeNode], level: int, maxLevel: int):\n        # Perform depth-first search to calculate removal depths\n        if not root:\n            return  # Base case: return if node is None\n        x = root.val  # Get the value of the current node\n\n        # Set the removal depth of the current node to maxLevel\n        self.removal[x] = maxLevel\n\n        # Recurse on the left child with an updated maxLevel that includes the right subtree height\n        self.dfs(root.left, level + 1, max(maxLevel, 1 + level + self.h(root.right)))\n\n        # Recurse on the right child with an updated maxLevel that includes the left subtree height\n        self.dfs(root.right, level + 1, max(maxLevel, 1 + level + self.h(root.left)))\n\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        # Prepare height and removal arrays\n        self.val2H = [-1] * self.N\n        self.removal = [-1] * self.N\n\n        # Compute removal depths for each node using DFS traversal\n        self.dfs(root, 0, 0)\n\n        # Retrieve the removal depths for each query\n        ans = [self.removal[q] for q in queries]\n        return ans\n\n```
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Recursion', 'Python3']