Python | Two pass solution | Beats 98% 🚀| O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe approach leverages a two-step process where it first calculates the height of subtr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe approach leverages a two-step process where it first calculates the height of subtrees for each node and stores these in a dictionary. It then iteratively updates this dictionary to ensure that each node\'s value reflects the maximum height observable from that node\'s position, using a depth-first traversal to propagate the maximum heights from the root downwards to all descendants. This ensures efficient query responses by precomputing necessary values.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- **Initialize Helper Functions**: The solution defines two helper functions within the treeQueries method. The first function, calcHeight, calculates the height of the tree from any given node and populates treeDict where each node\'s value is mapped to the height of its opposite subtree (left child\'s value maps to the right subtree height and vice versa). The second function, updateTreeDict, propagates the maximum heights found in the subtrees downward through the tree to potentially update the values in treeDict.\n\n- **Populate Tree Dictionary**: Using the calcHeight function, the algorithm first populates treeDict with initial values based on subtree heights. Each node\'s value is associated with the maximum height of the subtree opposite its child. For instance, if a node has a left child, the left child\'s value in treeDict is set to the height of the right subtree of the parent node.\n\n- **Update Tree Dictionary**: After the initial population, the updateTreeDict function is called to revise treeDict. This function ensures that each node in the tree has the correct maximum height value from its subtree by checking and updating treeDict values downward from the root, adjusting them based on the greater of the current value or the inherited maximum height from ancestor nodes.\n\n- **Answer Queries**: Finally, the method returns a list of heights for the nodes specified in the queries list by accessing the values in treeDict for each queried node value. This step directly uses the prepared treeDict to fetch and return the results efficiently.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        \n        def calcHeight(node, height):\n            if not node:\n                return height-1\n            leftH, rightH = calcHeight(node.left, height+1), calcHeight(node.right, height+1)\n            if node.left:\n                treeDict[node.left.val] = rightH\n            if node.right:\n                treeDict[node.right.val]=leftH\n            return max(leftH, rightH)\n\n        def updateTreeDict(node, maxheight):\n            if not node: return \n            if maxheight ==-2 or treeDict[node.val]>maxheight:\n                maxheight = treeDict[node.val]\n            if node.left and maxheight>treeDict[node.left.val]:\n                treeDict[node.left.val] = maxheight\n            if node.right and maxheight>treeDict[node.right.val]:\n                treeDict[node.right.val]= maxheight\n            updateTreeDict(node.left,  maxheight)\n            updateTreeDict(node.right, maxheight)\n        \n        treeDict=defaultdict(int)\n        calcHeight(root, 0)\n        updateTreeDict(root, -2)\n        return [treeDict[i] for i in queries]\n```\n![image.png](https://assets.leetcode.com/users/images/5bf9ec62-17f7-4997-be8b-4179559eb27a_1729915056.2717266.png)\n![image.png](https://assets.leetcode.com/users/images/e43ff954-0932-4d95-a072-21704bdd8b5e_1729915174.0036182.png)\n\n
['Dynamic Programming', 'Depth-First Search', 'Binary Tree', 'Python3']