Esta pregunta se formuló en una de las entrevistas: Dadas dos matrices no ordenadas, compruebe si creará la misma bst. por ejemplo: 2, 1, 4, 0 y 2, 1, 0, 4 formarán la misma BST.BST a partir de dos matrices no ordenadas
2
/\
1 4
/
0
por favor sugiero algo bueno.
Todos los elementos que son mayores, entonces el elemento raíz deben aparecer en el mismo orden en tanto los arrays
Y, por supuesto, la primera condición es que ambas matrices deben contener los mismos elementos, pero en orden diferente.
Por lo tanto esto puede ser resuelto en tiempo lineal.
Pseudocódigo sería así:
int GetNextIncresingElement(int[] arr, ref int index, int root)
{
for(int i = index; i< arr.Length; i++)
{
if(arr[i] > root)
{
index = i;
return arr[i];
}
}
return -1;
}
int GetNextDecreasingElement(int[] arr, ref int index, int root)
{
for(int i = index; i< arr.Length; i++)
{
if(arr[i] <= root)
{
index = i;
return arr[i];
}
}
return -1;
}
bool CheckFormsSameBST(int[] arr1, int[] arr2)
{
int index1 = 1;
int index2 = 1;
int num1;
int num2;
int root = arr1[0];
if(root != arr2[0])
return false;
while(true)
{
num1 = GetNextIncresingElement(arr1, ref index1, root);
num2 = GetNextIncresingElement(arr2, ref index2, root);
if(num1 != num2)
return false;
else
{
if(num1 == -1)
break;
}
index1++;
index2++;
}
index1 = 1;
index2 = 1;
while(true)
{
num1 = GetNextDecreasingElement(arr1, ref index1, root);
num2 = GetNextDecreasingElement(arr2, ref index2, root);
if(num1 != num2)
return false;
else
{
if(num1 == -1)
break;
}
index1++;
index2++;
}
return true;
}
Sus condiciones de pedido estricto cubren solo unos pocos casos. Considere: 'A1 = [2, 1, 4, 0, 3, 7]' y 'A2 = [2, 4, 1, 0, 7, 3]' – srbhkmr
¡No siempre funciona! Considere A1 = [8, 3, 6, 1, 4, 7, 10, 14, 13] y A2 = [8, 10, 14, 3, 6, 4, 1, 7, 13] – Srikrishnan
Puede consultar la explicación detallada que compara dos árboles binarios (no solo BST) en Determine if two binary trees are equal. Es fácil crear BST a partir de las matrices y luego ejecutar el algoritmo en las preguntas mencionadas.
IMO, puede ordenar una matriz y realizar una búsqueda binaria desde la segunda matriz hasta la ordenada, mientras tanto, asegúrese de estar utilizando cada elemento. Te costará mlogn.
compruebe el caso 2, 0, 1, 4. Primero ordénelo y luego busque en cada elemento de otro arreglo (2,1,0,4) en él. Encontrará todo el elemento y ambos no se formarán mismo BST. –
de verificación si se va a crear el mismo BST?
Sí.
comience a tomar el primer elemento como raíz y mantenga el número que es mayor que la raíz a la derecha y más pequeño que la raíz a la izquierda.
Si sigue el procedimiento anterior, observará que ambos árboles son idénticos.
Estoy de acuerdo con la idea descrita por Peter y Algorist. Pero creo que los subárboles de cada nodo (representados por la matriz menor que este nodo y la matriz más grande que ella) también deben examinarse de esta manera. Por ejemplo, 621407 y 621047 producen la misma BST pero 624017 no. La función puede escribirse recursivamente.
código de ejemplo ha añadido:
bool sameBST(int * t1, int * t2, int startPos, int endPos) {
int rootPos1, rootPos2;
if (endPos-startPos<0) return true;
if (t1[startPos]!=t2[startPos]) return false;
rootPos1=partition(t1,startPos,endPos,t1[startPos]);
rootPos2=partition(t2,startPos,endPos,t2[startPos]);
if (rootPos1!=rootPos2) return false;
return sameBST(t1,t2,startPos,rootPos1-1) && sameBST(t1,t2,rootPos1+1,endPos);
}
partición función es la misma que se utiliza en la clasificación rápida. Aparentemente, T (n) = 2T (n/2) + O (n), que conduce a la complejidad del tiempo T (n) = O (nlogn). Debido a la recursión, la complejidad espacio es O (log n)
El punto puede ser la de comparar permutaciones de los subsegmentos de una matriz con los respectivos subsegmentos de la otra matriz (piense orden de nivel):
comenzando con el primer elemento en la matriz, para i = 0 a algunos n, agrupe los elementos en conjuntos de 2^i
2^0 = 1: el primer elemento es la raíz - debe iniciar ambas matrices: [50].
2^1 = 2: cualquier permutación de los próximos 2 elementos está bien:
[25,75] or [75,25]
2^2 = 4: cualquier permutación de los próximos 4 elementos es bien:
[10, 35, 60, 85] or [60, 35, 10, 85] or ...
2^3 = 8: cualquier permutación de los siguientes 8 elementos es bien:
[5, 16, 30, 40, ….
así sucesivamente a 2^n hasta que las matrices están vacíos. respectivos subsegmentos deben tener la misma cantidad de elementos.
1) Ordene la matriz utilizando el recuento o la ordenación de radix.
2) Árbol de compilación utilizando nuestra matriz ordenada y matriz sin ordenar (para verificar el orden de inserción). Conservará la estructura del árbol.
3) Compare ambos árboles.
Todo se puede hacer en tiempo lineal - O (n).
Código:
import java.util.Arrays;
public class BSTFromUnsorted {
static class Node{
int key;
int arrivalTime,min,max,root;
Node left;
Node right;
Node(int k,int at){
key=k;left=null;right=null;arrivalTime=at;
}
}
public static void printTree(Node n){
if(n==null) return;
System.out.println(n.key+" "+ ((n.left!=null)?n.left.key:"-") + " " + ((n.right!=null)?n.right.key:"-"));
printTree(n.left);
printTree(n.right);
}
public static boolean compareTree(Node n1,Node n2){
if(n1==null && n2==null) return true;
return (n1!=null && n2!=null && n1.key==n2.key && compareTree(n1.left,n2.left) && compareTree(n1.right,n2.right)) ;
}
public static void main(String[] args){
int[] bstInsertOrder1={8, 10, 14, 3, 6, 4, 1, 7, 13};
int[] bstInsertOrder2={8, 3, 6, 1, 4, 7, 10, 14, 13};
Node n1 = buildBST(bstInsertOrder1);
printTree(n1);
System.out.println();
Node n2 = buildBST(bstInsertOrder2);
printTree(n2);
System.out.println("\nBoth are " + (compareTree(n1,n2)?"same":"different"));
}
public static Node buildBST(int[] insertOrder){
int length = insertOrder.length;
Node[] sortedOrder = new Node[length];
for(int i=0;i<length;i++){
sortedOrder[i] = new Node(insertOrder[i],i);
}
Radix.radixsort(sortedOrder,length);
int[] sortedIndex = new int[length];
for(int i=0;i<length;i++){
sortedOrder[i].max=sortedOrder[i].min=sortedOrder[i].root=i;
sortedIndex[sortedOrder[i].arrivalTime]=i;
}
for (int i=length-1;i>0;i--){
int j = sortedIndex[i];
int min=sortedOrder[j].min-1,max=sortedOrder[j].max+1;
Node n=null,n1;
if(min>=0){
n = sortedOrder[sortedOrder[min].root];
}
if(max<length){
n1=sortedOrder[sortedOrder[max].root];
if(n==null){
n=n1;
}
else{
n=(n.arrivalTime>n1.arrivalTime)?n:n1;
}
}
n1=sortedOrder[j];
if(n.key<n1.key){
n.right=n1;
n.max=n1.max;
sortedOrder[n.max].root=sortedOrder[n.min].root;
}
else{
n.left=n1;
n.min=n1.min;
sortedOrder[n.min].root=sortedOrder[n.max].root;
}
}
return sortedOrder[sortedIndex[0]];
}
static class Radix {
static int getMax(Node[] arr, int n) {
int mx = arr[0].key;
for (int i = 1; i < n; i++)
if (arr[i].key > mx)
mx = arr[i].key;
return mx;
}
static void countSort(Node[] arr, int n, int exp) {
Node output[] = new Node[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);
for (i = 0; i < n; i++)
count[(arr[i].key/exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i].key/exp) % 10] - 1] = arr[i];
count[(arr[i].key/exp) % 10]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
static void radixsort(Node[] arr, int n) {
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
}
}
"mismo BST": semánticamente [que contiene los mismos elementos] o estructuralmente [los dos árboles deben tener la misma estructura]? – amit
@amit, consulte el enlace mencionado por gaurav para ver qué significa si dos BST son iguales ... –
Me alegra que haya sido entendido, pero para la próxima vez, hay dos tipos de "igualdad", semántica y estructural, debe mencionar cuál buscas. – amit