Flattening the depth of tree and using range query
Intuition\n Describe your first thoughts on how to solve this problem. \nWe calculate the depth of every node and build a tree out of those nodes depths as thei
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe calculate the depth of every node and build a tree out of those nodes depths as their respective values. flatten the tree and calculate the maximum value of array while excluding the subarray which is the subtree of the given node.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O( N*log(N) )\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O( N )\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    vector<int> flatten, flatten_depth;\n    map<int,pair<int,int>> childCount;\n\n    int dfs( TreeNode* node, int depth ){\n        if( node == NULL ) return 0;\n        int left = dfs( node->left, depth + 1 );\n        flatten.push_back(node->val);\n        flatten_depth.push_back(depth);\n        int right = dfs(node->right, depth + 1 );\n        childCount[node->val] = {left, right};\n        return left + right + 1;\n    }\n\n    class SegmentTree{\n        int N;\n        vector<int> tree;\n        \n        public:\n        \n        SegmentTree(int _N){\n            N = _N;\n            int TREE_SIZE = 4 * N + 1;\n            tree.resize(TREE_SIZE);\n        }\n        \n        int build( int l, int r, int idx, vector<int> &v ){\n            if( l > r ) return INT_MIN;\n            if( l == r ) return tree[idx] = v[l];\n            int mid = l + ( r - l ) / 2;\n            int left = build( l , mid, idx * 2, v );\n            int right = build( mid + 1, r, idx * 2 + 1, v );\n            return tree[idx] = max( left, right );\n        }\n\n        int query( int l, int r, int idx, int left_bound, int right_bound ){\n            if( l > r ) return INT_MIN;\n            if( right_bound < l || r < left_bound ) return INT_MIN;\n            if( left_bound <= l && r <= right_bound ) return tree[idx];\n            int mid = l + ( r - l ) / 2;\n            int left = query( l, mid, idx * 2, left_bound, right_bound );\n            int right = query( mid+1, r, idx * 2 + 1, left_bound, right_bound );\n            return max( left, right );\n        }\n\n    };\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        dfs(root, 0);\n\n        int n = flatten.size();\n        map<int,int> nodeLoc;\n        for( int i = 0; i < n; i++ ){\n            nodeLoc[flatten[i]] = i;\n        }\n\n        SegmentTree tree = SegmentTree(n);\n        tree.build(0, n-1, 1, flatten_depth);\n\n        int m = queries.size();\n        vector<int> ans(m);\n\n        for( int i = 0; i < m; i++ ){\n            int node = queries[i];\n            int index = nodeLoc[node];\n            auto childs = childCount[node];\n            int left_bound = index - childs.first;\n            int right_bound = index + childs.second;\n            int left_val = tree.query( 0, n-1, 1, 0, left_bound-1 );\n            int right_val = tree.query( 0, n-1, 1, right_bound+1, n-1 );\n            int val = max( left_val, right_val );\n            ans[i] = val;\n        }\n\n        return ans;\n\n    }\n};\n```\n\n# Optimised by using prefix and suffix\n\n```cpp []\nclass Solution {\npublic:\n\n    vector<int> flatten, flattenDepth;\n    map<int,pair<int,int>> childCount;\n\n    int dfs( TreeNode* node, int depth ){\n        if( node == NULL ) return 0;\n        int left = dfs( node->left, depth + 1 );\n        flatten.push_back(node->val);\n        flattenDepth.push_back(depth);\n        int right = dfs(node->right, depth + 1 );\n        childCount[node->val] = {left, right};\n        return left + right + 1;\n    }\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        dfs(root, 0);\n\n        int n = flatten.size();\n        map<int,int> nodeLoc;\n        for( int i = 0; i < n; i++ ){\n            nodeLoc[flatten[i]] = i;\n        }\n\n        vector<int> left(n), right(n);\n        int maxi = INT_MIN;\n        for( int i = 0; i < n; i++ ) left[i] = (maxi = max( maxi, flattenDepth[i] ));\n        maxi = INT_MIN;\n        for( int i = n-1; i >= 0 ; i-- ) right[i] = (maxi = max( maxi, flattenDepth[i] ));\n\n        int m = queries.size();\n        vector<int> ans(m);\n\n        for( int i = 0; i < m; i++ ){\n            int node = queries[i];\n            int index = nodeLoc[node];\n            auto childs = childCount[node];\n            int left_bound = index - childs.first;\n            int right_bound = index + childs.second;\n            int left_val = left_bound > 0 ? left[left_bound-1] : INT_MIN;\n            int right_val = right_bound < n-1 ? right[right_bound+1] : INT_MIN ;\n            int val = max( left_val, right_val );\n            ans[i] = val;\n        }\n\n        return ans;\n\n    }\n};\n```\n\n\n\n
['C++']