Dadas dos arrays que representan una secuencia de claves. Imagine que hacemos un árbol de búsqueda binaria (BST) de cada array. Necesitamos decir si dos BST serán idénticos o no sin construir el árbol.
Ejemplo:
Por ejemplo, las arrays de entrada son {2, 4, 3, 1} y {2, 1, 4, 3} construirán el mismo árbol
Let the input arrays be a[] and b[] Example 1: a[] = {2, 4, 1, 3} will construct following tree. 2 / \ 1 4 / 3 b[] = {2, 4, 3, 1} will also construct the same tree. 2 / \ 1 4 / 3 So the output is "True" Example 2: a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13} b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13} They both construct the same following BST, so output is "True" 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13
Solución:
- De acuerdo con la propiedad BST, los elementos del subárbol izquierdo deben ser más pequeños y los elementos del subárbol derecho deben ser mayores que la raíz.
- Dos arreglos representan el mismo BST si, para cada elemento x, los elementos en los subárboles izquierdo y derecho de x aparecen después de él en ambos arreglos. Y lo mismo es cierto para las raíces de los subárboles izquierdo y derecho.
- La idea es verificar si los siguientes elementos más pequeños y más grandes son iguales en ambas arrays. Las mismas propiedades se verifican recursivamente para los subárboles izquierdo y derecho. La idea parece simple, pero la implementación requiere verificar todas las condiciones para todos los elementos. Lo que sigue es una interesante implementación recursiva de la idea.
Implementación:
C++
// A C++ program to check for Identical // BSTs without building the trees #include <bits/stdc++.h> using namespace std; /* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */ bool isSameBSTUtil(int a[], int b[], int n, int i1, int i2, int min, int max) { int j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j = i1; j < n; j++) if (a[j] > min && a[j] < max) break; for (k = i2; k < n; k++) if (b[k] > min && b[k] < max) break; /* If the parent element is leaf in both arrays */ if (j==n && k==n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decided by min and max values). The child found must be same in both arrays */ if (((j==n)^(k==n)) || a[j]!=b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Left Subtree } // A wrapper over isSameBSTUtil() bool isSameBST(int a[], int b[], int n) { return isSameBSTUtil(a, b, n, 0, 0, INT_MIN, INT_MAX); } // Driver code int main() { int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}; int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}; int n=sizeof(a)/sizeof(a[0]); if(isSameBST(a, b, n)) { cout << "BSTs are same"; } else { cout << "BSTs not same"; } return 0; } // This code is contributed by rathbhupendra
C
// A C program to check for Identical BSTs without building the trees #include<stdio.h> #include<limits.h> #include<stdbool.h> /* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */ bool isSameBSTUtil(int a[], int b[], int n, int i1, int i2, int min, int max) { int j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j=i1; j<n; j++) if (a[j]>min && a[j]<max) break; for (k=i2; k<n; k++) if (b[k]>min && b[k]<max) break; /* If the parent element is leaf in both arrays */ if (j==n && k==n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decided by min and max values). The child found must be same in both arrays */ if (((j==n)^(k==n)) || a[j]!=b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Left Subtree } // A wrapper over isSameBSTUtil() bool isSameBST(int a[], int b[], int n) { return isSameBSTUtil(a, b, n, 0, 0, INT_MIN, INT_MAX); } // Driver program to test above functions int main() { int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}; int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}; int n=sizeof(a)/sizeof(a[0]); printf("%s\n", isSameBST(a, b, n)? "BSTs are same":"BSTs not same"); return 0; }
Java
// A Java program to check for Identical // BSTs without building the trees class GFG { /* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */ static boolean isSameBSTUtil(int a[], int b[], int n, int i1, int i2, int min, int max) { int j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j = i1; j < n; j++) if (a[j] > min && a[j] < max) break; for (k = i2; k < n; k++) if (b[k] > min && b[k] < max) break; /* If the parent element is leaf in both arrays */ if (j == n && k == n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decided by min and max values). The child found must be same in both arrays */ if (((j==n)^(k==n)) || a[j]!=b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Left Subtree } // A wrapper over isSameBSTUtil() static boolean isSameBST(int a[], int b[], int n) { return isSameBSTUtil(a, b, n, 0, 0, Integer.MIN_VALUE,Integer.MAX_VALUE); } // Driver code public static void main(String[] args) { int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}; int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}; int n=a.length; System.out.printf("%s\n", isSameBST(a, b, n)? "BSTs are same":"BSTs not same"); } } /* This code contributed by PrinciRaj1992 */
Python3
# A Python3 program to check for Identical # BSTs without building the trees # # The main function that checks if two # arrays a[] and b[] of size n construct # same BST. The two values 'min' and 'max' # decide whether the call is made for left # subtree or right subtree of a parent # element. The indexes i1 and i2 are the # indexes in (a[] and b[]) after which we # search the left or right child. Initially, # the call is made for INT_MIN and INT_MAX # as 'min' and 'max' respectively, because # root has no parent. i1 and i2 are just # after the indexes of the parent element in a[] and b[]. */ def isSameBSTUtil(a, b, n, i1, i2, min, max): # # Search for a value satisfying the # constraints of min and max in a[] and # b[]. If the parent element is a leaf # node then there must be some elements # in a[] and b[] satisfying constraint. */ j, k = i1, i2 while j < n: if (a[j] > min and a[j] < max): break; j += 1 while k<n: if (b[k] > min and b[k] < max): break k += 1 # If the parent element is leaf in both arrays */ if (j == n and k == n): return True # Return false if any of the following is true # a) If the parent element is leaf in one array, # but non-leaf in other. # b) The elements satisfying constraints are # not same. We either search for left # child or right child of the parent # element (decided by min and max values). # The child found must be same in both arrays */ if (((j == n) ^ (k == n)) or a[j] != b[k]): return False # Make the current child as parent and # recursively check for left and right # subtrees of it. Note that we can also # pass a[k] in place of a[j] as they # are both are same */ return isSameBSTUtil(a, b, n, j + 1, k + 1, a[j], max) and isSameBSTUtil(a, b, n, j + 1, k + 1, min, a[j]) #Left Subtree # A wrapper over isSameBSTUtil() def isSameBST(a, b, n): return isSameBSTUtil(a, b, n, 0, 0, -10**9, 10**9) # Driver code if __name__ == '__main__': a = [8, 3, 6, 1, 4, 7, 10, 14, 13] b = [8, 10, 14, 3, 6, 4, 1, 7, 13] n = len(a) if(isSameBST(a, b, n)): print("BSTs are same") else: print("BSTs not same") # This code is contributed by mohit kumar 29.
C#
// C# program to check for Identical // BSTs without building the trees using System; class GFG { /* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */ static bool isSameBSTUtil(int []a, int []b, int n, int i1, int i2, int min, int max) { int j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j = i1; j < n; j++) if (a[j] > min && a[j] < max) break; for (k = i2; k < n; k++) if (b[k] > min && b[k] < max) break; /* If the parent element is leaf in both arrays */ if (j == n && k == n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decided by min and max values). The child found must be same in both arrays */ if (((j == n)^(k == n)) || a[j] != b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j + 1, k + 1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j + 1, k + 1, min, a[j]); // Left Subtree } // A wrapper over isSameBSTUtil() static bool isSameBST(int []a, int []b, int n) { return isSameBSTUtil(a, b, n, 0, 0, int.MinValue,int.MaxValue); } // Driver code public static void Main(String[] args) { int []a = {8, 3, 6, 1, 4, 7, 10, 14, 13}; int []b = {8, 10, 14, 3, 6, 4, 1, 7, 13}; int n=a.Length; Console.WriteLine("{0}\n", isSameBST(a, b, n)? "BSTs are same":"BSTs not same"); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // A Javascript program to check for Identical // BSTs without building the trees /* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */ function isSameBSTUtil(a,b,n,i1,i2,min,max) { let j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j = i1; j < n; j++) if (a[j] > min && a[j] < max) break; for (k = i2; k < n; k++) if (b[k] > min && b[k] < max) break; /* If the parent element is leaf in both arrays */ if (j == n && k == n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decided by min and max values). The child found must be same in both arrays */ if (((j==n)^(k==n)) || a[j]!=b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Left Subtree } // A wrapper over isSameBSTUtil() function isSameBST(a,b,n) { return isSameBSTUtil(a, b, n, 0, 0, Number.MIN_VALUE,Number.MAX_VALUE); } // Driver code let a=[8, 3, 6, 1, 4, 7, 10, 14, 13]; let b=[8, 10, 14, 3, 6, 4, 1, 7, 13]; let n=a.length; document.write( isSameBST(a, b, n)? "BSTs are same":"BSTs not same"); // This code is contributed by unknown2108 </script>
Producción
BSTs are same
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