Dado un árbol binario y un K objetivo , la tarea es encontrar el diámetro del subárbol mínimo que tiene una suma igual a K , que también es un árbol de búsqueda binaria. Devuelve -1 si no es posible.
Ejemplos:
Entrada: K = 38
13
/ \
5 23
/ \ / \
N 17 N N
/ \
16 N
Salida : 3
Explicación: 5, 17, 16 es el subárbol más pequeño con diámetro 3.Entrada: K = 73
7
/ \
N 23
/ \
10 23
/ \ / \
N 17 N N
Salida: -1
Explicación : ningún subárbol es BST para el objetivo dado.
Acercarse:
Este problema se puede resolver usando la idea de Programación Dinámica en Árboles . Almacene la suma y el diámetro de cada subárbol y verifique si un subárbol con suma K también es un árbol de búsqueda binaria o no.
Se pueden seguir los siguientes pasos para resolver este problema:
- Cree tablas Hash para almacenar la suma del subárbol, el diámetro del subárbol, el valor mínimo del subárbol y el valor máximo del subárbol.
- Inicialice la respuesta como infinito.
- Ahora almacene todos los valores en las tablas hash y verifique si el árbol binario dado es un BST utilizando el recorrido primero en profundidad.
- Durante el recorrido, solo se llenarán las tablas hash.
- Para que un binario sea un BST, se deben cumplir las siguientes 3 condiciones:
- El subárbol izquierdo y derecho debe ser BST.
- Valor máximo del subárbol izquierdo < valor del Node actual
- Valor mínimo del subárbol derecho > valor del Node actual
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement this approach
#include <bits/stdc++.h>
using namespace std;
// Structure of node of tree
struct Node {
int data;
Node* left;
Node* right;
Node(int num)
{
data = num;
left = NULL;
right = NULL;
}
};
int target, ans;
// Hash Tables to store Minimum value, Maximum Value,
// diameter of subtree and sum of elements of subtree
unordered_map<Node *, int> minv, maxv, h, sum;
// Function to check if the tree is a BST or not
bool isBST(Node* root)
{
// Base condition
if (root == NULL)
return true;
if (root->left == NULL
and root->right == NULL) {
minv[root] = root->data;
maxv[root] = root->data;
h[root] = 1;
sum[root] = root->data;
if (sum[root] == target)
ans = min(ans, h[root]);
return true;
}
// Condition for Binary tree to be a BST
if (root->left == NULL) {
if (isBST(root->right)
and minv[root->right] > root->data) {
minv[root] = root->data;
maxv[root] = maxv[root->right];
h[root] = h[root->right] + 1;
sum[root] = sum[root->right] + root->data;
if (sum[root] == target)
ans = min(ans, h[root]);
return true;
}
return false;
}
if (root->right == NULL) {
if (isBST(root->left)
and maxv[root->left] < root->data) {
minv[root] = minv[root->left];
maxv[root] = root->data;
h[root] = h[root->left] + 1;
sum[root] = sum[root->left] + root->data;
if (sum[root] == target)
ans = min(ans, h[root]);
return true;
}
return false;
}
bool bstleft = isBST(root->left);
bool bstright = isBST(root->right);
if (bstleft and bstright
and maxv[root->left] < root->data
and minv[root->right] > root->data) {
minv[root] = minv[root->left];
maxv[root] = maxv[root->right];
h[root] = 1 + h[root->left] + h[root->right];
sum[root] = root->data + sum[root->left]
+ sum[root->right];
if (sum[root] == target)
ans = min(ans, h[root]);
return true;
}
return false;
}
// Function to find the desired subtree
int minSubtreeSumBST(int k, Node* root)
{
// Initialize answer as infinity(INT_MAX)
ans = INT_MAX;
target = k;
// check for BST using DFS traversal
isBST(root);
if (ans == INT_MAX)
return -1;
return ans;
}
// Driver code
int main()
{
int k = 38;
// Defining tree
Node* root = new Node(13);
root->left = new Node(5);
root->right = new Node(23);
root->left->right = new Node(17);
root->left->right->left = new Node(16);
// Function call
int res = minSubtreeSumBST(k, root);
cout << res << endl;
return 0;
}
3
Complejidad del tiempo:O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA