트리를 구축하지 않고 동일한 BST 확인

문제 정책

"동일한 확인 BSTs without building the tree”문제는 배열 일부 노드를 나타냅니다. 따라서 두 어레이 모두에서 BST를 생성합니다. 이제 이러한 어레이에서 생성 된 BST가 동일한 지 여부를 알려야합니까? 여기서 문제는 나무를 만들 수 없다는 것입니다 (즉, 나무를 만들고 비교할 수 없다는 것입니다). 트리를 구성하지 않고 어떻게 든 같은지 확인해야합니다.

예

Arr1[] = {2, 1, 4, 3, 5}

Arr2[] = {2, 4, 5, 3, 1}

Yes

핀

설명 : 나무 건설에 관하여 b둘 다 똑같이 보이므로 동일하다고합니다.

나무를 만들지 않고 동일한 BST를 확인하기위한 접근 방식

이 문제를 해결하기 위해 재귀를 사용할 것입니다. 여기에서는 왼쪽 하위 트리의 모든 요소가 루트보다 작은 이진 검색 트리의 몇 가지 기본 속성을 사용합니다. 루트의 오른쪽에있는 모든 요소는 그것보다 큽니다. 따라서 두 트리의 루트가 동일한 지, 그리고 배열 시퀀스에서 루트의 자식이 그 뒤에 오는지 확인합니다. 따라서 루트는 두 배열의 자식 앞에 있습니다. 이 조건은 왼쪽 및 오른쪽 하위 트리에 대해서도 충족되어야합니다.

이것은 재귀 적으로 수행 될 수 있습니다. 따라서 우리는 왼쪽 하위 트리가 동일하고 오른쪽 하위 트리에 대해서도 동일한 지 확인하기 위해 자신을 호출하는 함수를 작성합니다. 이러한 모든 조건이 통과되면 두 배열이 나타내는 이진 검색 트리가 동일하다고 말합니다.

암호

트리를 빌드하지 않고 동일한 BST 확인을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// this function checks if the BSTs are identical or not
// Here the i1 & i2 represent the indices in the arrays arr1 and arr2
// The minimum & maximum are used for defining the bounds of left and right subtree
bool areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum)
{
    // find the first element in a which lies between minimum and maximum value
    // here we find the node which becomes the root of either the left or right subtree
    // depending upon the value of minimum and maximum
  int j, k;
  for (j = i1; j < n; j++)
  if (arr1[j] > minimum && arr1[j] < maximum)
    break;
  for (k = i2; k < n; k++)
    if (arr2[k] > minimum && arr2[k] < maximum)
      break;


    // base case
    // current node is a leaf in both the trees
    if (j==n && k==n)
        return true;

    bool oneLeafOtherNonLeaf = ((j==n)^(k==n));
    // current node is leaf in one of the trees but not in other.
    // the first number which satisfy the given constraint must be same in both the arrays
    // because they serve as root of the subtrees
    if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
        return false;

    // recursively solve for left and right subtree
    return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
}

int main()
{
    int arr1[] = {2, 1, 4, 3, 5};
    int arr2[] = {2, 4, 5, 3, 1};
  int n=sizeof(arr1)/sizeof(arr1[0]);
  bool answer = areBSTsIdentical(arr1, arr2, n, 0, 0, INT_MIN, INT_MAX);
  cout<<(answer ? "YES" : "NO");
  return 0;
}

YES

트리를 빌드하지 않고 동일한 BST 확인을위한 Java 코드

class Main
{ 

  // this function checks if the BSTs are identical or not
  // Here the i1 & i2 represent the indices in the arrays arr1 and arr2
  // The minimum & maximum are used for defining the bounds of left and right subtree
  static boolean areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum) 
  { 
    // find the first element in a which lies between minimum and maximum value
      // here we find the node which becomes the root of either the left or right subtree
      // depending upon the value of minimum and maximum
    int j, k;
    for (j = i1; j < n; j++)
    if (arr1[j] > minimum && arr1[j] < maximum)
      break;
    for (k = i2; k < n; k++)
      if (arr2[k] > minimum && arr2[k] < maximum)
        break;
  
  
      // base case
      // current node is a leaf in both the trees
      if (j==n && k==n)
          return true;
  
      boolean oneLeafOtherNonLeaf = ((j==n)^(k==n));
      // current node is leaf in one of the trees but not in other.
      // the first number which satisfy the given constraint must be same in both the arrays
      // because they serve as root of the subtrees
      if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
          return false;
  
      // recursively solve for left and right subtree
      return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
  } 
  
  public static void main(String[] args) 
  {
    int arr1[] = {2, 1, 4, 3, 5};
    	        int arr2[] = {2, 4, 5, 3, 1};
    int n=arr1.length; 
    boolean answer = areBSTsIdentical(arr1, arr2, n, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.print(answer ? "YES" : "NO");
  } 
}

YES

복잡성 분석

시간 복잡성

의 위에) 재귀를 호출했지만 두 배열을 모두 순회했기 때문입니다. 그러나 우리는 하나의 상태를 인덱스로 사용하여 배열에 대해 재귀를 실행하여 선형 시간 복잡성을 보장했습니다.

공간 복잡성

의 위에) 입력을 저장하기 위해 배열을 사용했기 때문입니다. 그 외에는 일정한 수의 변수를 사용했습니다. 따라서 알고리즘 자체는 O (1) 추가 공간 그러나 프로그램 전체는 선형 공간 복잡성을 가지고 있습니다.