algorithm - 来自两个未排序数组的 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;
}