주어진 배열이 이진 검색 트리의 Preorder Traversal을 나타낼 수 있는지 확인

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 링크드인
이진 검색 트리 스택 나무조회수 73

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

"주어진 배열이 이진 검색 트리의 사전 주문 순회를 나타낼 수 있는지 확인"문제는 선주문 순회 순서. 이제이 시퀀스를 고려하여이 시퀀스가 ​​이진 검색 트리를 나타낼 수 있는지 확인하십시오. 솔루션의 예상 시간 복잡성은 다음과 같습니다. O (1).

주어진 배열이 이진 검색 트리의 Preorder Traversal을 나타낼 수 있는지 확인

5 3 4 7 6 9 8 11
Yes

선주문 순서가 BST를 나타내는 지 확인하는 접근 방식

문제는 주어진 배열이 Preorder Traversal을 나타낼 수 있는지 확인하도록 요청합니다. 이진 검색 트리. 우리는 주어진 정수 정렬 입력으로. 이제이 배열에 선주문 순회 이진 검색 트리의 시퀀스입니다. 그런 다음 주어진 사전 주문 순회 시퀀스가 ​​이진 검색 트리를 나타낼 수 있는지 확인합니다.

순진한 접근 방식은 먼저 오른쪽의 현재 요소보다 더 큰 요소를 찾는 것입니다. 이제 오른쪽의 모든 요소가 선택한 현재 요소보다 큰지 확인하십시오. 그리고 큰 요소와 선택된 현재 요소의 왼쪽에있는 모든 요소는 그것보다 작습니다. 그런 다음 현재 요소에서 더 큰 요소보다 작은 요소까지 왼쪽 하위 배열에 대해 동일한 조건을 재귀 적으로 확인합니다. 그리고 또한 재귀 적으로 더 큰 요소에서 끝까지 하위 배열을 확인하십시오. 이 방법은 O (N ^ 2) 시간 복잡성이 필요하기 때문에 효율적이지 않습니다.

선형 시간으로 문제를 해결합니다. 우리는 찾아야 할 것입니다 스택을 사용하는 다음으로 큰 요소. 따라서 먼저 노드 값을 저장하는 스택을 만듭니다. 그런 다음 루트를 최소 정수 값으로 초기화합니다. 그런 다음 주어진 입력 배열로 시작하십시오. 스택 상단보다 큰 요소를 실행하는 경우. 그런 다음 현재 요소보다 크거나 스택이 비어있는 경우 스택이 맨 위에 올 때까지 요소를 계속 제거하십시오. 루트보다 작은 노드 값을 발견하면 사전 주문 순회가 올바르지 않습니다. 결국 우리가 이러한 조건을 통과 할 때. 현재 요소를 스택으로 푸시합니다.

암호

주어진 배열이 BST의 사전 주문 순회를 나타낼 수 있는지 확인하는 C ++ 코드

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

bool preorderBST(int input[], int n)
{
    stack<int> s;
    int root = INT_MIN;
    for(int i=0;i<n;i++)
    {
        // if current node is smaller than the root
        // the current node lies on the right of root
        // thus it is impossible for bst
        if (input[i] < root)
            return false;
        // keep removing elements smaller than the root
        // until you find an element which is greater than the root
        while(!s.empty() && s.top()<input[i])
            root = s.top(), s.pop();
        // if current element is smaller than the root
        // push it into stack
        s.push(input[i]);
    }
    // if we passed until the end of the array
    // that means that the given preorder sequence represents a valid BST
    return true;
}

int main()
{
    int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
    int n = (sizeof input)/(sizeof input[0]);

    cout<<((preorderBST(input, n)) ? "yes" : "no");
}
yes

주어진 배열이 BST의 사전 주문 순회를 나타낼 수 있는지 확인하는 Java 코드

import java.util.*;

class Main{
  static boolean preorderBST(int input[], int n)
  {
      Stack<Integer> s = new Stack<Integer>();
      int root = Integer.MIN_VALUE;
      for(int i=0;i<n;i++)
      {
          // if current node is smaller than the root
          // the current node lies on the right of root
          // thus it is impossible for bst
          if (input[i] < root)
              return false;
          // keep removing elements smaller than the root
          // until you find an element which is greater than the root
          while(!s.empty() && s.peek()<input[i]){
              root = s.peek();
              s.pop();
          }
          // if current element is smaller than the root
          // push it into stack
          s.push(input[i]);
      }
      // if we passed until the end of the array
      // that means that the given preorder sequence represents a valid BST
      return true;
  }

  public static void main(String[] args)
  {
      int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
      int n = input.length;

      System.out.print((preorderBST(input, n)) ? "yes" : "no");
  }
}
yes

복잡성 분석

시간 복잡성

의 위에), 주어진 입력 배열의 모든 인덱스를 순회했기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 스택을 사용했기 때문입니다. 따라서 최악의 경우 모든 노드를 저장할 수 있습니다.

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