1) Сортировка массива с использованием подсчета или сортировки по основанию.
2) Построить дерево, используя наш отсортированный массив и заданный несортированный массив (для проверки порядка вставки). Это сохранит структуру дерева.
3) Сравните оба дерева.
Все можно сделать за линейное время - O (n).
Код:
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);
}
}
}