Dado un árbol de búsqueda binario equilibrado (BST), escriba una función isTripletPresent() que devuelva verdadero si hay un triplete en BST dado con suma igual a 0, de lo contrario, devuelve falso. La complejidad de tiempo esperada es O (n ^ 2) y solo se puede usar O (Logn) espacio adicional. Puede modificar el árbol de búsqueda binaria dado. Tenga en cuenta que la altura de un BST equilibrado siempre es O (Inicio de sesión).
Por ejemplo, isTripletPresent() debería devolver verdadero para el siguiente BST porque hay un triplete con suma 0, el triplete es {-13, 6, 7}.
La solución de fuerza bruta es considerar cada triplete en BST y verificar si la suma suma cero. La complejidad temporal de esta solución será O(n^3).
Una mejor solución es crear una array auxiliar y almacenar el recorrido en orden de BST en la array. La array se ordenará como el recorrido en orden de BST siempre produce datos ordenados. Una vez que tenemos el recorrido Inorder, podemos usar el método 2 de esta publicación para encontrar el triplete con suma igual a 0. Esta solución funciona en tiempo O(n^2), pero requiere espacio auxiliar O(n).
La siguiente es la solución que funciona en tiempo O (n ^ 2) y usa espacio adicional O (Logn) :
- Convertir BST dado a lista doblemente enlazada (DLL)
- Ahora itere a través de cada Node de DLL y si la clave del Node es negativa, busque un par en DLL con una suma igual a la clave del Node actual multiplicada por -1. Para encontrar el par, podemos usar el enfoque utilizado en hasArrayTwoCandidates() en el método 1 de esta publicación.
Implementación:
C++
// A C++ program to check if there // is a triplet with sum equal to 0 in // a given BST #include <bits/stdc++.h> using namespace std; // A BST node has key, and left and right pointers class node { public: int key; node *left; node *right; }; // A function to convert given BST to Doubly // Linked List. left pointer is used // as previous pointer and right pointer // is used as next pointer. The function // sets *head to point to first and *tail // to point to last node of converted DLL void convertBSTtoDLL(node* root, node** head, node** tail) { // Base case if (root == NULL) return; // First convert the left subtree if (root->left) convertBSTtoDLL(root->left, head, tail); // Then change left of current root // as last node of left subtree root->left = *tail; // If tail is not NULL, then set right // of tail as root, else current // node is head if (*tail) (*tail)->right = root; else *head = root; // Update tail *tail = root; // Finally, convert right subtree if (root->right) convertBSTtoDLL(root->right, head, tail); } // This function returns true if there // is pair in DLL with sum equal to given // sum. The algorithm is similar to hasArrayTwoCandidates() // in method 1 of http://tinyurl.com/dy6palr bool isPresentInDLL(node* head, node* tail, int sum) { while (head != tail) { int curr = head->key + tail->key; if (curr == sum) return true; else if (curr > sum) tail = tail->left; else head = head->right; } return false; } // The main function that returns // true if there is a 0 sum triplet in // BST otherwise returns false bool isTripletPresent(node *root) { // Check if the given BST is empty if (root == NULL) return false; // Convert given BST to doubly linked list. head and tail store the // pointers to first and last nodes in DLLL node* head = NULL; node* tail = NULL; convertBSTtoDLL(root, &head, &tail); // Now iterate through every node and // find if there is a pair with sum // equal to -1 * head->key where head is current node while ((head->right != tail) && (head->key < 0)) { // If there is a pair with sum // equal to -1*head->key, then return // true else move forward if (isPresentInDLL(head->right, tail, -1*head->key)) return true; else head = head->right; } // If we reach here, then // there was no 0 sum triplet return false; } // A utility function to create // a new BST node with key as given num node* newNode(int num) { node* temp = new node(); temp->key = num; temp->left = temp->right = NULL; return temp; } // A utility function to insert a given key to BST node* insert(node* root, int key) { if (root == NULL) return newNode(key); if (root->key > key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } // Driver code int main() { node* root = NULL; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)) cout << "Present"; else cout << "Not Present"; return 0; } // This code is contributed by rathbhupendra
C
// A C program to check if there is a triplet with sum equal to 0 in // a given BST #include<stdio.h> // A BST node has key, and left and right pointers struct node { int key; struct node *left; struct node *right; }; // A function to convert given BST to Doubly Linked List. left pointer is used // as previous pointer and right pointer is used as next pointer. The function // sets *head to point to first and *tail to point to last node of converted DLL void convertBSTtoDLL(node* root, node** head, node** tail) { // Base case if (root == NULL) return; // First convert the left subtree if (root->left) convertBSTtoDLL(root->left, head, tail); // Then change left of current root as last node of left subtree root->left = *tail; // If tail is not NULL, then set right of tail as root, else current // node is head if (*tail) (*tail)->right = root; else *head = root; // Update tail *tail = root; // Finally, convert right subtree if (root->right) convertBSTtoDLL(root->right, head, tail); } // This function returns true if there is pair in DLL with sum equal // to given sum. The algorithm is similar to hasArrayTwoCandidates() // in method 1 of http://tinyurl.com/dy6palr bool isPresentInDLL(node* head, node* tail, int sum) { while (head != tail) { int curr = head->key + tail->key; if (curr == sum) return true; else if (curr > sum) tail = tail->left; else head = head->right; } return false; } // The main function that returns true if there is a 0 sum triplet in // BST otherwise returns false bool isTripletPresent(node *root) { // Check if the given BST is empty if (root == NULL) return false; // Convert given BST to doubly linked list. head and tail store the // pointers to first and last nodes in DLLL node* head = NULL; node* tail = NULL; convertBSTtoDLL(root, &head, &tail); // Now iterate through every node and find if there is a pair with sum // equal to -1 * head->key where head is current node while ((head->right != tail) && (head->key < 0)) { // If there is a pair with sum equal to -1*head->key, then return // true else move forward if (isPresentInDLL(head->right, tail, -1*head->key)) return true; else head = head->right; } // If we reach here, then there was no 0 sum triplet return false; } // A utility function to create a new BST node with key as given num node* newNode(int num) { node* temp = new node; temp->key = num; temp->left = temp->right = NULL; return temp; } // A utility function to insert a given key to BST node* insert(node* root, int key) { if (root == NULL) return newNode(key); if (root->key > key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } // Driver program to test above functions int main() { node* root = NULL; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)) printf("Present"); else printf("Not Present"); return 0; }
Java
// A Java program to check if there // is a triplet with sum equal to 0 in // a given BST import java.util.*; class GFG { // A BST node has key, and left and right pointers static class node { int key; node left; node right; }; static node head; static node tail; // A function to convert given BST to Doubly // Linked List. left pointer is used // as previous pointer and right pointer // is used as next pointer. The function // sets *head to point to first and *tail // to point to last node of converted DLL static void convertBSTtoDLL(node root) { // Base case if (root == null) return; // First convert the left subtree if (root.left != null) convertBSTtoDLL(root.left); // Then change left of current root // as last node of left subtree root.left = tail; // If tail is not null, then set right // of tail as root, else current // node is head if (tail != null) (tail).right = root; else head = root; // Update tail tail = root; // Finally, convert right subtree if (root.right != null) convertBSTtoDLL(root.right); } // This function returns true if there // is pair in DLL with sum equal to given // sum. The algorithm is similar to hasArrayTwoCandidates() // in method 1 of http://tinyurl.com/dy6palr static boolean isPresentInDLL(node head, node tail, int sum) { while (head != tail) { int curr = head.key + tail.key; if (curr == sum) return true; else if (curr > sum) tail = tail.left; else head = head.right; } return false; } // The main function that returns // true if there is a 0 sum triplet in // BST otherwise returns false static boolean isTripletPresent(node root) { // Check if the given BST is empty if (root == null) return false; // Convert given BST to doubly linked list. head and tail store the // pointers to first and last nodes in DLLL head = null; tail = null; convertBSTtoDLL(root); // Now iterate through every node and // find if there is a pair with sum // equal to -1 * head.key where head is current node while ((head.right != tail) && (head.key < 0)) { // If there is a pair with sum // equal to -1*head.key, then return // true else move forward if (isPresentInDLL(head.right, tail, -1*head.key)) return true; else head = head.right; } // If we reach here, then // there was no 0 sum triplet return false; } // A utility function to create // a new BST node with key as given num static node newNode(int num) { node temp = new node(); temp.key = num; temp.left = temp.right = null; return temp; } // A utility function to insert a given key to BST static node insert(node root, int key) { if (root == null) return newNode(key); if (root.key > key) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; } // Driver code public static void main(String[] args) { node root = null; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)) System.out.print("Present"); else System.out.print("Not Present"); } } // This code is contributed by aashish1995
Python3
# A Python program to check if there # is a triplet with sum equal to 0 in # a given BST # A BST Node has key, and left and right pointers class Node: def __init__(self): self.key = 0; self.left = None; self.right = None; head = Node(); tail = Node(); # A function to convert given BST to Doubly # Linked List. left pointer is used # as previous pointer and right pointer # is used as next pointer. The function # sets *head to point to first and *tail # to point to last Node of converted DLL def convertBSTtoDLL(root): # Base case if (root == None): return; global tail; global head; # First convert the left subtree if (root.left != None): convertBSTtoDLL(root.left); # Then change left of current root # as last Node of left subtree root.left = tail; # If tail is not None, then set right # of tail as root, else current # Node is head if (tail != None): (tail).right = root; else: head = root; # Update tail tail = root; # Finally, convert right subtree if (root.right != None): convertBSTtoDLL(root.right); # This function returns True if there # is pair in DLL with sum equal to given # sum. The algorithm is similar to hasArrayTwoCandidates() # in method 1 of http:#tinyurl.com/dy6palr def isPresentInDLL(head, tail, s): while (head != tail): curr = head.key + tail.key; if (curr == s): return True; elif(curr > s): tail = tail.left; else: head = head.right; return False; # The main function that returns # True if there is a 0 sum triplet in # BST otherwise returns False def isTripletPresent(root): # Check if the given BST is empty if (root == None): return False; # Convert given BST to doubly linked list. head and tail store the # pointers to first and last Nodes in DLLL global tail; global head; head = None; tail = None; convertBSTtoDLL(root); # Now iterate through every Node and # find if there is a pair with sum # equal to -1 * head.key where head is current Node while ((head.right != tail) and (head.key < 0)): # If there is a pair with sum # equal to -1*head.key, then return # True else move forward if (isPresentInDLL(head.right, tail, -1 * head.key)): return True; else: head = head.right; # If we reach here, then # there was no 0 sum triplet return False; # A utility function to create # a new BST Node with key as given num def newNode(num): temp = Node(); temp.key = num; temp.left = temp.right = None; return temp; # A utility function to insert a given key to BST def insert(root, key): if (root == None): return newNode(key); if (root.key > key): root.left = insert(root.left, key); else: root.right = insert(root.right, key); return root; # Driver code if __name__ == '__main__': root = None; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)): print("Present"); else: print("Not Present"); # This code is contributed by Rajput-Ji
C#
// A C# program to check if there // is a triplet with sum equal to 0 in // a given BST using System; public class GFG { // A BST node has key, and left and right pointers public class node { public int key; public node left; public node right; }; static node head; static node tail; // A function to convert given BST to Doubly // Linked List. left pointer is used // as previous pointer and right pointer // is used as next pointer. The function // sets *head to point to first and *tail // to point to last node of converted DLL static void convertBSTtoDLL(node root) { // Base case if (root == null) return; // First convert the left subtree if (root.left != null) convertBSTtoDLL(root.left); // Then change left of current root // as last node of left subtree root.left = tail; // If tail is not null, then set right // of tail as root, else current // node is head if (tail != null) (tail).right = root; else head = root; // Update tail tail = root; // Finally, convert right subtree if (root.right != null) convertBSTtoDLL(root.right); } // This function returns true if there // is pair in DLL with sum equal to given // sum. The algorithm is similar to hasArrayTwoCandidates() // in method 1 of http://tinyurl.com/dy6palr static bool isPresentInDLL(node head, node tail, int sum) { while (head != tail) { int curr = head.key + tail.key; if (curr == sum) return true; else if (curr > sum) tail = tail.left; else head = head.right; } return false; } // The main function that returns // true if there is a 0 sum triplet in // BST otherwise returns false static bool isTripletPresent(node root) { // Check if the given BST is empty if (root == null) return false; // Convert given BST to doubly linked list. head and tail store the // pointers to first and last nodes in DLLL head = null; tail = null; convertBSTtoDLL(root); // Now iterate through every node and // find if there is a pair with sum // equal to -1 * head.key where head is current node while ((head.right != tail) && (head.key < 0)) { // If there is a pair with sum // equal to -1*head.key, then return // true else move forward if (isPresentInDLL(head.right, tail, -1*head.key)) return true; else head = head.right; } // If we reach here, then // there was no 0 sum triplet return false; } // A utility function to create // a new BST node with key as given num static node newNode(int num) { node temp = new node(); temp.key = num; temp.left = temp.right = null; return temp; } // A utility function to insert a given key to BST static node insert(node root, int key) { if (root == null) return newNode(key); if (root.key > key) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; } // Driver code public static void Main(String[] args) { node root = null; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)) Console.Write("Present"); else Console.Write("Not Present"); } } // This code is contributed by aashish1995
Javascript
<script> // A JavaScript program to check if there // is a triplet with sum equal to 0 in // a given BST // A BST node has key, // and left and right pointers class node { constructor(val) { this.key = val; this.left = null; this.right = null; } } var head; var tail; // A function to convert given BST to Doubly // Linked List. left pointer is used // as previous pointer and right pointer // is used as next pointer. The function // sets *head to point to first and *tail // to point to last node of converted DLL function convertBSTtoDLL( root) { // Base case if (root == null) return; // First convert the left subtree if (root.left != null) convertBSTtoDLL(root.left); // Then change left of current root // as last node of left subtree root.left = tail; // If tail is not null, then set right // of tail as root, else current // node is head if (tail != null) (tail).right = root; else head = root; // Update tail tail = root; // Finally, convert right subtree if (root.right != null) convertBSTtoDLL(root.right); } // This function returns true if there // is pair in DLL with sum equal to given // sum. The algorithm is // similar to hasArrayTwoCandidates() // in method 1 of http://tinyurl.com/dy6palr function isPresentInDLL( head, tail , sum) { while (head != tail) { var curr = head.key + tail.key; if (curr == sum) return true; else if (curr > sum) tail = tail.left; else head = head.right; } return false; } // The main function that returns // true if there is a 0 sum triplet in // BST otherwise returns false function isTripletPresent( root) { // Check if the given BST is empty if (root == null) return false; // Convert given BST to doubly // linked list. head and tail store the // pointers to first and last nodes in DLLL head = null; tail = null; convertBSTtoDLL(root); // Now iterate through every node and // find if there is a pair with sum // equal to -1 * head.key where // head is current node while ((head.right != tail) && (head.key < 0)) { // If there is a pair with sum // equal to -1*head.key, then return // true else move forward if (isPresentInDLL(head.right, tail, -1 * head.key)) return true; else head = head.right; } // If we reach here, then // there was no 0 sum triplet return false; } // A utility function to create // a new BST node with key as given num function newNode(num) { var temp = new node(); temp.key = num; temp.left = temp.right = null; return temp; } // A utility function to insert a given key to BST function insert( root , key) { if (root == null) return newNode(key); if (root.key > key) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; } // Driver code var root = null; root = insert(root, 6); root = insert(root, -13); root = insert(root, 14); root = insert(root, -8); root = insert(root, 15); root = insert(root, 13); root = insert(root, 7); if (isTripletPresent(root)) document.write("Present"); else document.write("Not Present"); // This code contributed by gauravrajput1 </script>
Present
Tenga en cuenta que la solución anterior modifica el BST dado.
Complejidad del tiempo: el tiempo necesario para convertir BST a DLL es O (n) y el tiempo necesario para encontrar el triplete en DLL es O (n ^ 2).
Espacio auxiliar: el espacio auxiliar solo se necesita para la pila de llamadas de funciones en la función recursiva convertBSTtoDLL(). Dado que el árbol dado está equilibrado (la altura es O (Inicio de sesión)), la cantidad de funciones en la pila de llamadas nunca será mayor que O (Inicio de sesión).
También podemos encontrar triplete en mismo tiempo y espacio extra sin modificar el árbol. Ver siguiente publicación. El código discutido allí también se puede usar para encontrar trillizos.
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