Dado un árbol de búsqueda binario que contiene valores enteros positivos mayores que 0, la tarea es verificar si el BST contiene un callejón sin salida o no. Aquí Dead End significa que no podemos insertar ningún elemento después de ese Node.
Ejemplos:
Input : 8
/ \
5 9
/ \
2 7
/
1
Output : Yes
Explanation : Node "1" is the dead End because
after that we cant insert any element.
Input : 8
/ \
7 10
/ / \
2 9 13
Output : Yes
Explanation : We can't insert any element at
node 9.
Si observamos más de cerca el problema, podemos notar que básicamente necesitamos verificar si hay un Node hoja con valor x tal que x+1 y x-1 existen en BST con la excepción de x = 1. Para x = 1, no podemos insertar 0 porque la declaración del problema dice que BST contiene solo números enteros positivos.
Para implementar la idea anterior, primero recorremos todo el BST y almacenamos todos los Nodes en un conjunto. También almacenamos todas las hojas en un hash separado para evitar volver a atravesar BST. Finalmente, verificamos para cada Node hoja x, si x-1 y x+1 están presentes en el conjunto o no.
A continuación se muestra una implementación en C++ de la idea anterior.
C++
// C++ program check whether BST contains
// dead end or not
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new node
Node *newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new Node
with given key in BST */
struct Node* insert(struct Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
// Function to store all node of given binary search tree
void storeNodes(Node * root, unordered_set<int> &all_nodes,
unordered_set<int> &leaf_nodes)
{
if (root == NULL)
return ;
// store all node of binary search tree
all_nodes.insert(root->data);
// store leaf node in leaf_hash
if (root->left==NULL && root->right==NULL)
{
leaf_nodes.insert(root->data);
return ;
}
// recur call rest tree
storeNodes(root-> left, all_nodes, leaf_nodes);
storeNodes(root->right, all_nodes, leaf_nodes);
}
// Returns true if there is a dead end in tree,
// else false.
bool isDeadEnd(Node *root)
{
// Base case
if (root == NULL)
return false ;
// create two empty hash sets that store all
// BST elements and leaf nodes respectively.
unordered_set<int> all_nodes, leaf_nodes;
// insert 0 in 'all_nodes' for handle case
// if bst contain value 1
all_nodes.insert(0);
// Call storeNodes function to store all BST Node
storeNodes(root, all_nodes, leaf_nodes);
// Traversal leaf node and check Tree contain
// continuous sequence of
// size tree or Not
for (auto i = leaf_nodes.begin() ; i != leaf_nodes.end(); i++)
{
int x = (*i);
// Here we check first and last element of
// continuous sequence that are x-1 & x+1
if (all_nodes.find(x+1) != all_nodes.end() &&
all_nodes.find(x-1) != all_nodes.end())
return true;
}
return false ;
}
// Driver program
int main()
{
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
Node *root = NULL;
root = insert(root, 8);
root = insert(root, 5);
root = insert(root, 2);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 11);
root = insert(root, 4);
if (isDeadEnd(root) == true)
cout << "Yes " << endl;
else
cout << "No " << endl;
return 0;
}
Python3
# Python 3 program check
# whether BST contains
# dead end or not
all_nodes = set()
leaf_nodes = set()
# A BST node
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
''' A utility function to
insert a new Node with
given key in BST '''
def insert(node, key):
'''/* If the tree is empty,
return a new Node */ '''
if (node == None):
return newNode(key)
# Otherwise, recur down
# the tree
if (key < node.data):
node.left = insert(node.left,
key)
else if (key > node.data):
node.right = insert(node.right,
key)
# return the (unchanged)
# Node pointer
return node
# Function to store all node
# of given binary search tree
def storeNodes(root):
global all_nodes
global leaf_nodes
if (root == None):
return
# store all node of binary
# search tree
all_nodes.add(root.data)
# store leaf node in leaf_hash
if (root.left == None and
root.right == None):
leaf_nodes.add(root.data)
return
# recur call rest tree
storeNodes(root. left)
storeNodes(root.right)
# Returns true if there is
# a dead end in tree,
# else false.
def isDeadEnd(root):
global all_nodes
global leaf_nodes
# Base case
if (root == None):
return False
# create two empty hash
# sets that store all BST
# elements and leaf nodes
# respectively.
# insert 0 in 'all_nodes'
# for handle case if bst
# contain value 1
all_nodes.add(0)
# Call storeNodes function
# to store all BST Node
storeNodes(root)
# Traversal leaf node and
# check Tree contain
# continuous sequence of
# size tree or Not
for x in leaf_nodes:
# Here we check first and
# last element of continuous
# sequence that are x-1 & x+1
if ((x + 1) in all_nodes and
(x - 1) in all_nodes):
return True
return False
# Driver code
if __name__ == '__main__':
'''/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
'''
root = None
root = insert(root, 8)
root = insert(root, 5)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 11)
root = insert(root, 4)
if(isDeadEnd(root) == True):
print("Yes")
else:
print("No")
# This code is contributed by bgangwar59
Yes
Complejidad de tiempo : O(n)
Enfoque mejorado
En el enfoque anterior, estamos usando 2 hashmaps, uno para almacenar todos los Nodes y otro para almacenar los Nodes hoja, en lugar de usar 2 mapas, podemos resolver este problema con 1 hashmap también.
Podemos pasar el hashmap de todos los Nodes y verificar si para el Node x existe un x-1 y x+1 o no. Si tenemos un Node para el cual x+1 y x-1 están presentes, devolveremos verdadero; de lo contrario, devolveremos falso
Implementación:
C++
// C++ program check whether BST contains
// dead end or not
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new node
Node *newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new Node
with given key in BST */
struct Node* insert(struct Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
void findallNodes(Node* root,map<int,int> &allnodes)
{
if(root == NULL)
return ;
allnodes[root->data] = 1;
findallNodes(root->left,allnodes);
findallNodes(root->right,allnodes);
}
bool check(Node* root,map<int,int> &allnodes)
{
if(root == NULL)
return false;
if(root->left == NULL and root->right == NULL)
{
int pre = root->data - 1;
int next = root->data + 1;
if(allnodes.find(pre) != allnodes.end() and allnodes.find(next) != allnodes.end())
return true;
}
return check(root->left,allnodes) or check(root->right,allnodes);
}
bool isDeadEnd(Node *root)
{
// Base case
if (root == NULL)
return false ;
map<int,int> allnodes;
// adding 0 for handling the exception of node having data = 1
allnodes[0] = 1;
findallNodes(root,allnodes);
return check(root,allnodes);
}
// Driver program
int main()
{
/* 8
/ \
5 11
/ \
2 7
\
3
\
4 */
Node *root = NULL;
root = insert(root, 8);
root = insert(root, 5);
root = insert(root, 2);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 11);
root = insert(root, 4);
if (isDeadEnd(root) == true)
cout << "Yes " << endl;
else
cout << "No " << endl;
return 0;
}
Yes
Solución recursiva simple para verificar si BST contiene callejón sin salida
Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA