DFS | C++ | Explained with Picutes
Explanation:\nAs shown in below picture, we do a pre-order traveral and mark indices.\n\n\n\n\nSimultaneously, store the depths of each node in same order of th
Explanation:\nAs shown in below picture, we do a pre-order traveral and mark indices.\n\n![image](https://assets.leetcode.com/users/images/415ff652-3ef3-4d4a-be3c-0839370ae4b7_1667102528.0020385.png)\n\n\nSimultaneously, store the depths of each node in same order of their indices.\n![image](https://assets.leetcode.com/users/images/724123cc-18e0-4a05-a912-2e7729c86fad_1667102536.2512622.png)\nNow, follow the steps to get the answer:\n1. We calculate the number of nodes under each node using simple dfs in O(n)\n2. Create two arrays left_max, right_max. Store the prefix maximum in left_max and suffix maximum in right_max.\n3. Since we have the index of the node and the number of nodes under it, we can easily calculate the subarray of indices that needs to be excluded.\nFor example, \nIf we queries[i] = 2,\nits index is 2.\n\nSo we query the maximum in the subarray of (0, 1) and (5, 8)\nWe excluded (2, 4) because, 2 is starting index and it has 3 nodes under it.\nFor more calarity, look at picture below:\n![image](https://assets.leetcode.com/users/images/ecb360db-a62e-49d2-b0c2-c316645af361_1667102688.4487271.png)\n\nFinally after max query, we store the answer in array and we return it.\n\nCode:\n\n```\nclass Solution {\npublic:\n    int n = 0;\n    map<int, int> idx_map;\n    map<int, int> nodes_under_me;\n    vector<int> depths, right_max, left_max;\n    void dfs(TreeNode *root, int depth){\n        if(!root)   return;\n        idx_map[root->val] = n++;\n        depths.push_back(depth);\n        dfs(root -> left, depth + 1);\n        dfs(root -> right, depth + 1);\n    }\n    \n    int calc_nodes_under_me(TreeNode *root){\n        if(!root)   return 0;\n        nodes_under_me[root->val] = calc_nodes_under_me(root->left) + calc_nodes_under_me(root->right) + 1;\n        return nodes_under_me[root->val];\n    }\n    \n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        int i, st, en, curr_ans;\n        vector<int> ans;\n        dfs(root, 0);\n        calc_nodes_under_me(root);\n        left_max.push_back(depths[0]);  right_max.push_back(depths[n-1]);\n        for(i=1;i<n;i++)    left_max.push_back(max(left_max.back(), depths[i])), right_max.push_back(max(right_max.back(), depths[n-i-1]));\n        reverse(right_max.begin(), right_max.end());\n        \n        for(i=0;i<queries.size();i++){\n            en = idx_map[queries[i]] - 1;\n            st = en + 1 + nodes_under_me[queries[i]];\n            curr_ans = left_max[en];\n            if(st < n)  curr_ans = max(curr_ans, right_max[st]);\n            ans.push_back(curr_ans);\n        }        \n        return ans;\n    }\n};\n```\n\nThank you. Encourage me to post such solutions by upvoting this post.\n
[]