Dado un árbol binario que consta de N Nodes con valores en el rango [0, N – 1] arraigados como 0 , una array wt[] de tamaño N donde wt[i] es el peso del i -ésimo Node y una array 2D Q [][] que consta de consultas del tipo {L, R} , la tarea de cada consulta es encontrar la suma de los pesos de todos los Nodes cuyo ancho vertical se encuentra en el rango [L, R] .
Ejemplos:
Entrada: N = 4, wt[] = {1, 2, 3, 4}, Q[][] = {{0, 1}, {1, 1}}
0(1)
/ \
3(4) 1(2)
/
2(3)
Salida:
6
10
Explicación:
Para Consulta 1: El rango es [0, 1]
- Nodes en la posición de ancho 0: 0, 2. Por lo tanto, la suma de los Nodes es 1 + 3 = 4.
- Nodes en la posición de ancho 1: 1. Por lo tanto, la suma de los Nodes es 2.
Por lo tanto, la suma de los pesos de todos los Nodes = 4 + 2 = 6.
Para la consulta 2: el rango es [-1, 1]
- Los Nodes en la posición de ancho -1 son 3. Por lo tanto, la suma de los Nodes es 4.
- Nodes en la posición de ancho 0: 0, 2. Por lo tanto, la suma de los Nodes es 1 + 3 = 4.
- Nodes en la posición de ancho 1: 1. Por lo tanto, la suma de los Nodes es 2.
Por lo tanto, la suma de los pesos de todos los Nodes = 4 + 4 + 2 = 10.
Entrada: N= 8, wt[] = {8, 6, 4, 5, 1, 2, 9, 1}, Q[][] = {{-1, 1}, {-2, -1}, {0, 3}}
1
/ \
3 2
/ \ \
5 6 4
/ \
7 0
Salida:
25
7
29
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es realizar un recorrido en el árbol para cada consulta y luego imprimir la suma de los pesos de todos los Nodes que se encuentran en el rango dado [L, R] .
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar precalculando la suma de pesos para cada posición de ancho y almacenándolos en un mapa M , luego encuentre la suma de prefijos de la array recién creada para procesar las consultas en tiempo constante. Siga los pasos a continuación para resolver el problema:
- Realice el recorrido DFS en el árbol dado y actualice la suma en todas las posiciones de ancho y guárdelas en un mapa M realizando las siguientes operaciones:
- Inicialmente, la posición pos de la raíz es 0 .
- En cada llamada recursiva , actualice el peso del Node en M actualizando M[pos] = M[pos] + wt[node] .
- Llame recursivamente a su hijo izquierdo decrementando pos en 1 .
- Llame recursivamente a su hijo derecho incrementando pos en 1 .
- Itere sobre el mapa M y actualice el valor de cada par clave-valor a la suma de los valores anteriores que ocurrieron.
- Ahora, recorra la array Consultas[] y para cada consulta [L, R] , imprima el valor de (M[R] – M[L – 1]) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create new node
Node* newNode(int d)
{
Node* n = new Node;
n->data = d;
n->left = NULL;
n->right = NULL;
return n;
}
// Function to pre-compute the sum of
// weights at each width position
void findwt(Node* root, int wt[],
map<int, int>& um,
int width = 0)
{
// Base Case
if (root == NULL) {
return;
}
// Update the current width
// position weight
um[width] += wt[root->data];
// Recursive Call to its left
findwt(root->left, wt, um,
width - 1);
// Recursive Call to its right
findwt(root->right, wt, um,
width + 1);
}
// Function to find the sum of the
// weights of nodes whose vertical
// widths lies over the range [L, R]
// for Q queries
void solveQueries(int wt[], Node* root,
vector<vector<int> > queries)
{
// Stores the weight sum
// of each width position
map<int, int> um;
// Function Call to fill um
findwt(root, wt, um);
// Stores the sum of all previous
// nodes, while traversing Map
int x = 0;
// Traverse the Map um
for (auto it = um.begin();
it != um.end(); it++) {
x += it->second;
um[it->first] = x;
}
// Iterate over all queries
for (int i = 0;
i < queries.size(); i++) {
int l = queries[i][0];
int r = queries[i][1];
// Print the result for the
// current query [l, r]
cout << um[r] - um[l - 1]
<< "\n";
}
}
// Driver Code
int main()
{
int N = 8;
// Given Tree
Node* root = newNode(1);
root->left = newNode(3);
root->left->left = newNode(5);
root->left->right = newNode(6);
root->right = newNode(2);
root->right->right = newNode(4);
root->right->right->left = newNode(7);
root->right->right->right = newNode(0);
int wt[] = { 8, 6, 4, 5, 1, 2, 9, 1 };
vector<vector<int> > queries{ { -1, 1 },
{ -2, -1 },
{ 0, 3 } };
solveQueries(wt, root, queries);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Structure of a node
static class Node
{
int data;
Node left;
Node right;
}
// Function to create new node
static Node newNode(int d)
{
Node n = new Node();
n.data = d;
n.left = null;
n.right = null;
return n;
}
// Function to pre-compute the sum of
// weights at each width position
static void findwt(Node root, int wt[],
TreeMap<Integer, Integer> um,
int width)
{
// Base Case
if (root == null)
{
return;
}
// Update the current width
// position weight
if (um.containsKey(width))
{
um.put(width, um.get(width) +
wt[root.data]);
}
else
{
um.put(width, wt[root.data]);
}
// Recursive Call to its left
findwt(root.left, wt, um,
width - 1);
// Recursive Call to its right
findwt(root.right, wt, um,
width + 1);
}
// Function to find the sum of the
// weights of nodes whose vertical
// widths lies over the range [L, R]
// for Q queries
static void solveQueries(int wt[], Node root,
int[][] queries)
{
// Stores the weight sum
// of each width position
TreeMap<Integer,
Integer> um = new TreeMap<Integer,
Integer>();
// Function Call to fill um
findwt(root, wt, um, 0);
// Stores the sum of all previous
// nodes, while traversing Map
int x = 0;
// Traverse the Map um
for(Map.Entry<Integer, Integer> it : um.entrySet())
{
x += it.getValue();
um.put(it.getKey(), x);
}
// Iterate over all queries
for(int i = 0; i < queries.length; i++)
{
int l = queries[i][0];
int r = queries[i][1];
// Print the result for the
// current query [l, r]
int ans = 0;
if (um.containsKey(r))
{
ans = um.get(r);
}
if (um.containsKey(l - 1))
{
ans -= um.get(l - 1);
}
System.out.println(ans);
}
}
// Driver Code
public static void main(String[] args)
{
int N = 8;
// Given Tree
Node root = newNode(1);
root.left = newNode(3);
root.left.left = newNode(5);
root.left.right = newNode(6);
root.right = newNode(2);
root.right.right = newNode(4);
root.right.right.left = newNode(7);
root.right.right.right = newNode(0);
int wt[] = { 8, 6, 4, 5, 1, 2, 9, 1 };
int queries[][] = { { -1, 1 },
{ -2, -1 },
{ 0, 3 } };
solveQueries(wt, root, queries);
}
}
// This code is contributed by Dharanendra L V.
25 7 29
Complejidad temporal: O(N*log N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA