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

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

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

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

차례

예

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

1 -4 0 2 7

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

핀

Array = {1 , 2 , 3}

2 1 3

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

핀

접근하다(재귀)

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

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

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

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

암호알고리즘

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

정렬 된 배열을 이진 검색 트리 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. 두 재귀 함수에서 트리가 높이 균형을 이루는 지 확인하므로 최대 값을 사용합니다. 오) 재귀 스택 프레임을위한 공간.

Twitter Facebook 링크드인 버퍼 레딧 텀블러