정렬 된 배열을 이진 검색 트리 Leetcode 솔루션으로 변환

난이도 쉽게
자주 묻는 질문 어도비 벽돌 Airbnb 아마존 Apple 블룸버그 게시물에서 시스코 구글 Microsoft 신탁 스포티 파이 VM웨어 Yahoo
알고리즘 이진 검색 트리 코딩 깊이 우선 검색 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 83

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

우리가 정렬 된 것을 고려하십시오 정렬 정수 목표는 트리가 높이 균형을 이루도록이 배열에서 이진 검색 트리를 구축하는 것입니다. 트리에있는 노드의 왼쪽 및 오른쪽 하위 트리의 높이 차이가 최대 1 인 경우 트리는 높이 균형을 이룬다 고합니다.

여러 솔루션이있을 수 있다는 것을 쉽게 찾을 수 있습니다. 유효한 해결책을 찾아야합니다. 이 문제에서 우리는 트리를 인쇄 할 필요가없고 생성 할 필요가 있습니다. 사전 주문 순회를 인쇄하기 만하면됩니다.

Array = {-4 , 0 , 1 , 2 , 7}
1 -4 0 2 7

설명 : BST는 다음과 같습니다.

정렬 된 배열을 이진 검색 트리 Leetcode 솔루션으로 변환

 

Array = {1 , 2 , 3}
2 1 3

설명 : BST는 다음과 같습니다.

정렬 된 배열을 이진 검색 트리 Leetcode 솔루션으로 변환

접근하다(재귀)

우리는 두 가지를 추적해야합니다.

  1. 모든 노드에는 왼쪽 자식으로 더 작은 요소가 있어야하며 오른쪽 자식에 대해서는 그 반대의 경우도 마찬가지입니다.
  2. BST는 높이 균형이 있어야합니다.

언제든지 트리의 균형을 유지하려면 배열의 중간 요소를 루트로 선택해야합니다. 이런 식으로 우리는 1 배열의 크기가 짝수이고 높이 차이가 다음과 같은 경우 왼쪽 및 오른쪽 하위 트리 사이 배열이 홀수 일 때.

이제 중간 노드를 루트로 선택하면 왼쪽 하위 배열에서 왼쪽 하위 트리를 만들고 오른쪽 하위 배열에서 오른쪽 하위 트리를 만들어야합니다. 이것은 원래 문제의 하위 문제이므로 재귀 적으로 해결할 수 있습니다. 왼쪽 및 오른쪽 하위 트리를 중간 노드에 할당 한 후이를 반환하고 이진 검색 트리의 postorder traversal을 인쇄 할 수 있습니다.

암호알고리즘

  1. 다른 기능 생성 converArrayToBST () 주어진 배열의 특정 범위를 변환하고 해당 BST 루트 노드를 반환합니다.
  2. 위에서 언급 한 범위에서 L = 배열의 왼쪽 한계, R = 배열의 오른쪽 한계라고합시다.
    1. L> R 인 경우
      • 반환 NULL, 잘못된 범위를 수신하므로
    2. L == R 인 경우
      • 다음과 같은 값을 가진 새 노드를 반환합니다. 배열 [L] 
    3. 이 범위의 중간 노드를 다음과 같이 찾으십시오. 중간 = (L + (R – L) / 2)
      • 다음과 같은 값을 가진 새 BST 노드로 헤드를 초기화하십시오. 어레이 [중간]
      • 양수인 왼쪽 (left)연락해주세요 왼쪽 및 오른쪽 하위 범위에서 각각 호출되는 동일한 함수로 하위 트리
      • 리턴 헤드
  3. 이진 검색 트리의 선주문 순회 인쇄

정렬 된 배열을 이진 검색 트리 Leetcode 솔루션으로 변환 구현

정렬 된 배열을 이진 검색 트리로 변환하는 C ++ 솔루션

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

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

BSTNode* convertArrayToBST(vector <int> &a , int l , int r)
{
    if(l > r)
        return NULL;
    if(l == r)
        return new BSTNode(a[l]);
    int mid = (l + (r - l) / 2);
    BSTNode* head = new BSTNode(a[mid]);
    head->left = convertArrayToBST(a , l , mid - 1);
    head->right = convertArrayToBST(a , mid + 1 , r);
    return head;
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
    int n = a.size();
    return convertArrayToBST(a , 0 , n - 1);
}

void preorder(BSTNode* head)
{
    if(!head)
        return;
    cout << head->value << " ";
    preorder(head->left);
    preorder(head->right);
}


int main()
{
    vector <int> a = {-4 , 0 , 1 , 2 , 7};
    BSTNode* head = sortedArrayToBST(a);
    preorder(head);
    return 0;
}

정렬 된 배열을 이진 검색 트리로 변환하는 Java 솔루션

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int x)
    {
        value = x;
        left = null;
        right = null;
    }
}

class convert_array_to_BST
{
    public static void main(String args[])
    {
        int[] a = {-4 , 0 , 1 , 2 , 7};
        BSTNode head = sortedArrayToBST(a);
        preorder(head);
    }

    static BSTNode convertArrayToBST(int[] a , int l , int r)
    {
        if(l > r)
            return null;
        if(l == r)
            return new BSTNode(a[l]);
        int mid = (l + (r - l) / 2);
        BSTNode head = new BSTNode(a[mid]);
        head.left = convertArrayToBST(a , l , mid - 1);
        head.right = convertArrayToBST(a , mid + 1 , r);
        return head;
    }

    static BSTNode sortedArrayToBST(int[] a)
    {
        return convertArrayToBST(a , 0 , a.length - 1);
    }

    static void preorder(BSTNode head)
    {
        if(head == null)
            return;
        System.out.print(head.value + " ");
        preorder(head.left);
        preorder(head.right);
    }
}
1 -4 0 2 7

정렬 된 배열을 이진 검색 트리 Leetcode 솔루션으로 변환하는 복잡성 분석

시간 복잡성

의 위에), N = 트리의 요소 수. BST를 구성하고 선주문 순회를 인쇄하기 위해 모든 요소를 ​​방문합니다.

공간 복잡성

오), 여기서 H = 나무의 높이 = 로그N. 두 재귀 함수에서 트리가 높이 균형을 이루는 지 확인하므로 최대 값을 사용합니다. 오) 재귀 스택 프레임을위한 공간.

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