BST来自​​两个未排序的数组

Question

在一次采访中询问了这个问题:给定两个未排序的数组,检查它是否会创建相同的bst.例如:2,1,4,0​​和2,1,0,4都将形成相同的BST.

     2
    / \
   1   4
  /
 0

请建议一些好的算法.

Answer 1

• 取第一个元素 - 这将是根（在上面的例子中是 2）
• 所有小于根元素的元素在两个数组中应以相同的顺序出现
  • 在上面的例子中，0和1是小于根元素的元素。
  • 第一个数组中的顺序是 1、0
  • 第二个数组中保持相同的顺序。所以两者形成相同的结构

• 所有大于根元素的元素应以相同的顺序出现在两个数组中

  • 在上面的示例中，4 是唯一大于 2 的元素。它出现在两个数组中。因此，这两个数组都会创建结构相同的 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;
}