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

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 링크드 인
이진 검색 트리 스택 나무조회수 38
링크드 인버퍼레딧텀블러

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