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