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


난이도 중급
자주 묻는 질문 광신자 Fourkites
이진 검색 트리 이진 트리 나무

문제 정책

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

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

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

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

설명 : 나무 건설에 관하여 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) 추가 공간 그러나 프로그램 전체는 선형 공간 복잡성을 가지고 있습니다.