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

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"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 »