BST从两个排序的数组

这个问题被问在采访中的一个：给定两个排序的数组，检查它是否会产生相同的BST。例如：2,1,4,0和2,1,0,4将形成相同的BST。BST从两个排序的数组

请提出了一些很好的算法中。

来源

2012-03-22 algo-geeks

“相同BST”：语义[包含相同的元素]或结构上[两棵树应具有相同的结构]？ – amit 2012-03-22 08:14:42

@amit请参考由gaurav提到的链接，看看两个BST是否相等意味着什么。 – 2012-03-22 08:36:35

我很高兴你明白了 - 但下一次有两种“平等” - 语义和结构 - 你应该提到哪一个你正在寻找。 – amit 2012-03-22 08:39:21

拍摄第一元件 - 这将是根（在上面的情况下，它是2时）
所有其比根元素较少的元素应该出现在相同的顺序在两个阵列
- 在上面的例子中，0和1是比根元素更小的元素。
- 在第一阵列的顺序是1，0
- 相同的顺序被维持在第二阵列英寸因此，无论形成同一结构
所有这一切都大于根元素应该出现在相同的顺序在两个阵列中的元件
- 在上述实施例4是唯一的元件大于它出现在两个阵列中。因此，这两个阵列创建结构相同的BST。
当然的非常第一条件是，无论是阵列应包含相同的元素，但以不同的顺序。

因此，这可以在线性时间内解决。

伪代码会是这样的：

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; 
}

来源

2012-03-22 10:02:30 Algorist

您的严格订购条件仅涵盖少数情况。考虑：'A1 = [2,1,4,0,3,7]'和A2 = [2,4,1,0,7,3]' – srbhkmr 2012-03-22 15:30:35

并不总是奏效！考虑A1 = [8,3,6,1,4,7,10,14,13]和A2 = [8,10,14,3,6,4,1,7,13] – Srikrishnan 2015-10-24 23:39:39

您可以在Determine if two binary trees are equal查看详细的解释比较两个二进制树（不只是BST）。从阵列中创建BST很容易，然后在上述问题中运行算法。

来源

2012-03-22 06:28:27

IMO，您可以排序一个数组并从第二数组排序数组的二进制搜索，同时，请确保您使用的每一个元素。它会花费你mlogn。

来源

2012-03-22 06:54:21 DarthVader

检查案例2,0,1,4。首先对它进行排序，然后搜索其中的另一个数组（2,1,0,4）的每个元素，您将找到所有元素，并且它们都不会形成同样的BST。 – 2012-03-22 07:15:44

检查它是否会产生相同的BST？

是的。

开始以第一元素作为根，并保持其大于根向右和比根小，以左边的数字。

，如果你按照上面的过程，你会发现，无论是树木是相同的。

来源

2012-03-22 12:08:29 Vijay

我同意Peter和Algorist所描述的想法。但是我相信每个节点的子树（用小于这个节点的数组表示，大于它的数组表示）也需要以这种方式来检查。例如，621407和621047产生相同的BST，但624017不产生相同的BST。该函数可以递归编写。

示例代码添加：

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); 
}

功能分区是你在快速排序使用同一个。显然，T（n）= 2T（n/2）+ O（n），这导致时间复杂度T（n）= O（nlogn）。由于递归的，空间复杂度是O（logn）时间

来源

2012-03-22 15:23:27 HelloWorld

点可以以比较一个阵列与其它阵列的各子段的子段的排列（水平认为顺序）：

从数组中的第一个元素开始，对于i = 0到某个n，将组中的元素分组为2^i

2^0 = 1：第一个元素是根 - 必须同时启动两个数组： [50]。

2^1 = 2：下一个2个元素的任何排列是细：

[25,75] or [75,25]

2^2 = 4：在接下来的4个元件的任何排列是细：

[10, 35, 60, 85] or [60, 35, 10, 85] or ...

2^3 = 8：接下来的8个元素的任何排列都很好：

[5, 16, 30, 40, ….

等到2^n，直到数组为空。各个子段必须具有相同数量的元素。

来源

2012-03-22 22:13:09 kasavbere

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); 
    } 
} 

}

来源

2016-07-23 09:34:26 tejram

BST从两个排序的数组

回答

相关问题