주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인하십시오.

난이도 쉽게
자주 묻는 질문 아마존 시트릭스 IBM 과연 정보 가장자리 오요 룸 테라 데이타
이진 검색 트리 이진 트리 열 나무 트리 순회조회수 71

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

문제 정책

"주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인"문제는 이진 검색 트리. 그리고 레벨 순서 순회 나무의. 레벨 순서 순회가 이진 검색 트리를 나타낼 수 있는지 여부를 효율적으로 찾아야합니까?

예

Level Order Traversal - {5 2 7 1 6 9 }
True

 

주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인하십시오.핀

설명

주어진 레벨 순서 순회는 이미지에 표시된 이진 트리를 나타냅니다. 그리고 우리가 볼 수 있듯이 트리는 이진 트리의 모든 속성을 충족하므로 출력이 참입니다.

주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인하는 방법

순진한 접근

순진한 접근 방식은 주어진 레벨 순서를 만족하는 모든 바이너리 트리를 만들려고 할 때일 수 있습니다. 그런 다음 트리가 이진 검색 트리를 나타내는 지 확인하십시오. 그러나이 작업은 비용이 많이 듭니다. 우선 우리는 많은 나무를 건설 할 것입니다. 그런 다음 알고리즘은 형성된 트리가 BST인지 확인해야합니다. 그래서 우리는 나무를 만들 필요가없는 곳에서 무언가를해야합니다.

효율적인 접근

효율적인 접근 방식은 레벨 순서 순회에서 발생하는 각 요소의 경계를 저장합니다. 이러한 경계는 하위 트리 요소가 놓일 수있는 경계를 나타냅니다. 노드에 대해 이야기하면 최소값과 최대 값이 있습니다. 왼쪽 하위 트리에는 최소 경계에서 현재 노드 값 -1까지의 요소가 포함될 수 있습니다. 오른쪽 하위 트리의 요소는 현재 노드 값 +1에서 최대 경계까지의 범위를 가질 수 있습니다.

따라서 우리는 이러한 경계를 가진 요소를 계속 삽입하고 모든 노드를 통과 할 수있는 경우 대기열을 사용할 것입니다. 우리는 주어진 레벨 순서 순회가 BST를 나타낼 수 있다고 말합니다. 알고리즘은 이진 트리가 BST인지 여부를 확인하는 것과 매우 유사합니까?

암호

주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인하는 C ++ 코드

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

struct node{
    int data;
    int mn;
    int mx;
};

node create(int data, int mn, int mx){
    node tmp;
    tmp.data = data;
    tmp.mn = mn;
    tmp.mx = mx;
    return tmp;
}

bool checkLevelOrderTraversalRepresentBinarySearchTree(vector<int> traversal){
    queue<node> q;
    int i = 0, n = traversal.size();
    q.push(create(traversal[i++], INT_MIN, INT_MAX));

    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
            q.push(create(traversal[i++], now.mn, now.data));
        if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
            q.push(create(traversal[i++], now.data, now.mx));
    }
    return (i == n);
}

int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> traversal(n);
        for(int i=0;i<n;i++)
            cin>>traversal[i];
        cout<<(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no")<<endl;
    }
}

1
6
5 2 7 1 6 9
true

주어진 배열이 이진 검색 트리의 레벨 순서 순회를 나타낼 수 있는지 확인하는 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int mn;
  int mx;
}

class Main{
  
  static node create(int data, int mn, int mx){
      node tmp = new node();
      tmp.data = data;
      tmp.mn = mn;
      tmp.mx = mx;
      return tmp;
  }
  
  static boolean checkLevelOrderTraversalRepresentBinarySearchTree(int traversal[]){
      Queue<node> q = new LinkedList<node>();
      int i = 0; int n = traversal.length;
      q.add(create(traversal[i++], Integer.MIN_VALUE, Integer.MAX_VALUE));
  
      while(q.size() > 0){
          node now = q.peek();
          q.remove();
          if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
              q.add(create(traversal[i++], now.mn, now.data));
          if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
              q.add(create(traversal[i++], now.data, now.mx));
      }
      return (i == n);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-- > 0){
          int n = sc.nextInt();
          int[] traversal = new int[n];
          for(int i=0;i<n;i++)
              traversal[i] = sc.nextInt();
          System.out.println(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no");
      }
  }
}
1
6
5 2 7 1 6 9
true

복잡성 분석

시간 복잡성

우리는 단순히 요소를 탐색했습니다. 최악의 경우에는 모든 요소를 ​​탐색해야합니다. 알고리즘은 선형 시간 복잡도를 갖습니다. 의 위에).

공간 복잡성

알고리즘이 선형 공간 복잡성을 갖도록 만든 요소를 ​​저장하기 위해 큐를 사용했습니다. 의 위에).

균열 시스템 설계 인터뷰
Translate »