DFS x2 computes heights||24ms Beats 96.70%
Intuition\n Describe your first thoughts on how to solve this problem. \n Hard qestions. Since the constraints\n> 2 <= n <= 10^5\n1 <= Node.val <= n\nAll the va
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n Hard qestions. Since the constraints\n> 2 <= n <= 10^5\n1 <= Node.val <= n\nAll the values in the tree are unique.\n\nC-arrays are used, not the hash maps. 2x DFS, 1 DFS+memo for computing the heights, 2 for the heights with removing subtrees rooted at every tree node.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Declare arrays `val2H[N], removal[N]`\n2. Define the 1st DFS function `int h(TreeNode* root)` to compute the height `val2H[x]` for `x=root->val`.(All the values in the tree are unique)\n3. Define the 2nd DFS function `dfs(TreeNode* root, int level, int maxLevel)` to set `removal[root->val]=maxLevel` if removing subtree rooted at the current node `root`.  That calls recursively for left-subtree in the parameter for `maxlevel=max(maxLevel, 1+level+h(root->right))`& similar way for the right-subtree.\n4. In `vector<int> treeQueries(TreeNode* root, vector<int>& queries) `  set the initial values for `val2H, removal` filled with -1\n5. Proceed `dfs(root, 0, 0)`\n6. Use a loop to assign `ans[i++]=removal[q]` for `q` in `queries`.\n7. return `ans`\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N+|queries|)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(100001)$ where `N=max(height)<=100000`\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nconst int N=100001;\nclass Solution {\npublic:\n    int val2H[N], removal[N];\n    int h(TreeNode* root){\n        if (!root) return -1;\n        int x=root->val;\n        if (val2H[x]!=-1) return val2H[x];\n        return val2H[x]=1+max(h(root->left), h(root->right));\n    }\n\n    void dfs(TreeNode* root, int level, int maxLevel){\n        if (!root) return;\n        int x=root->val;\n        removal[x]=maxLevel;\n        dfs(root->left, level+1, max(maxLevel, 1+level+h(root->right)));\n        dfs(root->right, level+1, max(maxLevel, 1+level+h(root->left)));\n    }\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        memset(val2H, -1, sizeof(val2H));\n        memset(removal, -1, sizeof(removal));\n        dfs(root, 0, 0);\n\n        vector<int> ans(queries.size());\n        int i=0;\n        for(int q: queries)\n            ans[i++]=removal[q];\n        return ans;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n![Leetcode2024_300.png](https://assets.leetcode.com/users/images/a0fbb283-d703-4286-9dcd-008a989d4f75_1729902803.4733257.png)\n
['Array', 'Tree', 'Depth-First Search', 'Memoization', 'Binary Tree', 'C++']