BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인

난이도 쉽게
자주 묻는 질문 Accenture 아마존 모노 타입 솔루션 페이팔 Synopsys
이진 검색 트리 이진 트리 나무조회수 33

문제 정책

"BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인"문제는 이진 검색 트리의 사전 주문 순회가 제공된다는 것을 나타냅니다. 그리고 모든 비 리프 노드에 단일 자식 만 포함되어 있는지 찾아야합니다. 여기서 우리는 또한 주어진 입력의 모든 노드가 고유 한 값을 가지고 있음을 고려합니다.

BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인

 

Preorder Traversal: 6 15 7 9 11
Yes

설명 : 위 이미지에서 볼 수 있듯이 주어진 사전 주문 순회가있는 트리에는 각 내부 노드에 대해 하나의 자식이 있습니다. 따라서 출력은 예입니다.

BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하는 방법

순회 선주문 루트에 우선권이 주어지고 왼쪽 및 오른쪽 하위 트리 앞에 인쇄됨을 의미합니다. 따라서 루트 뒤의 요소는 루트보다 작거나 큽니다. 따라서 주어진 시퀀스가 ​​사전 주문인지 확인해야하는 경우 이진 검색 트리. 두 개의 중첩 루프를 사용하여 주어진 시퀀스로 이진 검색 트리를 만들 수 있는지 확인할 수 있습니다.

순진한 접근

이미 논의했듯이, 사전 주문 순회는 상단에 루트를 포함하고 왼쪽 및 오른쪽 하위 트리가 인쇄 된 후. 이제이 작업이 완료되었습니다. 재귀 적으로 트리의 모든 노드가 덮일 때까지. 따라서 주어진 시퀀스가 ​​BST를 나타내는 지 확인할 수 있습니다. 외부 루프가 루트를 선택하는 데 사용되는 두 개의 중첩 루프를 실행합니다. 그리고 중첩 루프는 그 뒤의 요소가 왼쪽 및 오른쪽 하위 트리를 나타낼 수 있는지 확인합니다. 이를 위해 특정 인덱스까지 모든 요소가 선택한 요소보다 작은 지 확인합니다. 그 이후의 요소는 선택한 요소보다 큽니다. 이제 사용 사례에 따라이 접근 방식을 수정할 수 있습니다.

BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하기 위해 알고리즘을 수정하는 방법을 살펴 보겠습니다. BST의 내부 자식에 정확히 한 명의 자식이있는 경우. 이는 각 내부 노드가 왼쪽 하위 트리 또는 오른쪽 하위 트리를 가질 수 있음을 의미합니다. 동시에 두 하위 트리를 모두 포함하지는 않습니다. 따라서 알고리즘을 요약합니다. 외부 루프가 요소를 선택하는 두 개의 중첩 루프를 사용합니다. 그런 다음 중첩 된 루프를 사용하여 그 뒤에 오는 요소가 하위 트리에 속하는지 확인합니다. 이전에는 요소가 루트보다 작은 특정 인덱스가 있고 그 뒤에 요소가 루트보다 큽니다. 이제 우리는 그러한 색인을 찾을 수 없습니다. 그러나이 방법은 다항식 시간 복잡도가 O (N ^ 2)이기 때문에 충분히 효율적이지 않습니다.

효율적인 접근

지금까지 모든 노드의 모든 자식이이 문제에 따라 현재 노드보다 작거나 클 것이라는 점을 분명히했습니다. 따라서 BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하기 위해 현재 노드의 다음 사전 주문 후속 작업을 찾습니다. 그런 다음 현재 노드의 마지막 사전 주문 후계자를 찾습니다. 두 후속 작업이 현재 노드보다 작거나 현재 노드보다 큰 경우. 그런 다음 계속 진행하면 요소 중 하나가 현재 노드보다 작기 때문에 현재 노드에 왼쪽 및 오른쪽 하위 트리가 모두 있다는 것을 알고 있습니다. 그리고 다른 노드는 현재 노드보다 큽니다. 따라서 우리는 요구 사항에 따라 false 또는 -1을 반환합니다.

암호

BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하는 C ++ 코드

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

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하는 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

복잡성 분석

시간 복잡성

O (N), 우리는 방금 preorder 배열을 순회했기 때문에. 그리고 사전 주문 배열에는 N 개의 요소가 있으므로 선형 시간 복잡성이 있습니다.

공간 복잡성

O (N), 재귀 스택에 필요한 공간이며, 사전 주문 시퀀스를 저장하기 위해 크기 N의 입력 배열도 사용했습니다.

Translate »