시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
균형 잡힌 BST 문제에 대한 정렬 된 배열에서 우리는 정렬 정렬 된 순서로 균형 이진 검색 구성 나무 정렬 된 배열에서.
차례
예
입력
arr [] = {1, 2, 3, 4, 5}
산출
선주문 : 3 2 1 5 4
입력
arr [] = {7, 11, 13, 20, 22, 41}
산출
선주문 : 20 11 7 13
암호알고리즘
또한 순회 순회 이진 검색 트리의 결과는 정렬 된 데이터가됩니다. 여기에 정렬 된 배열이 주어지고이를 Balanced Binary Search Tree로 변환해야합니다.
배열의 중간 요소가 균형 이진 검색 트리의 루트를 형성하고 배열의 왼쪽에있는 요소가 균형 BST의 왼쪽 하위 트리를 형성하고 중간 요소의 오른쪽에있는 요소를 형성 함을 알 수 있습니다. 균형 잡힌 BST의 오른쪽 하위 트리를 형성합니다. 이 절차를 왼쪽 및 오른쪽 하위 트리에서 반복적으로 반복하면 균형 잡힌 이진 검색 트리가 생성됩니다.
Sorted의 경우와 마찬가지로 연결된 목록 Balanced BST의 경우 연결 목록에서 중간 요소를 찾는 데 O (n) 시간 복잡성이 필요하지만 배열의 경우 배열의 임의 액세스 속성으로 인해 복잡성이 O (1)로 줄어 듭니다. . 따라서 연결된 목록의 경우 순진한 접근 방식이 배열의 경우 최적의 접근 방식이됩니다.
- 배열의 중간 요소를 찾고 인덱스를 mid가되도록합니다.
- 인덱스 중간에있는 요소는 균형 잡힌 BST의 루트를 형성합니다.
- 중간의 왼쪽에있는 요소는 왼쪽 하위 트리를 형성하므로 왼쪽 하위 트리에 대해이 함수를 재귀 적으로 호출합니다.
- 중간의 오른쪽에있는 요소는 오른쪽 하위 트리를 형성하므로 오른쪽 하위 트리에 대해서도이 함수를 재귀 적으로 호출합니다.
- 루트를 반환합니다.
시간 복잡성 = O (N)
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 주어진 배열의 크기입니다.
정렬 된 배열을 균형 BST로 변환하기위한 JAVA 코드
public class SortedArrayToBalancedBST {
// class representing node of a binary tree
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
// function to print the preorder traversal of a binary tree
private static void preorder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
}
private static Node convertSortedArrayToBalancedBST(int[] arr, int start, int end) {
// Base Case
if (start > end) {
return null;
}
// find the middle element of the array
int mid = (start + end) / 2;
// the middle element forms the root of the balanced BST
Node root = new Node(arr[mid]);
// elements to the left of mid forms the left subtree
root.left = convertSortedArrayToBalancedBST(arr, start, mid - 1);
// elements to the right of mid forms the right subtree
root.right = convertSortedArrayToBalancedBST(arr, mid + 1, end);
// return root
return root;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[] {1, 2, 3, 4, 5};
Node root1 = convertSortedArrayToBalancedBST(arr1, 0, arr1.length - 1);
preorder(root1);
System.out.println();
// Example 2
int arr2[] = new int[] {7, 11, 13, 20, 22, 41};
Node root2 = convertSortedArrayToBalancedBST(arr2, 0,arr2.length - 1);
preorder(root2);
System.out.println();
}
}
3 1 2 4 5 13 7 11 22 20 41
정렬 된 배열을 균형 BST로 변환하기위한 C ++ 코드
#include <iostream>
using namespace std;
// class representing node of a binary tree
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = right = NULL;
}
};
// function to print the preorder traversal of a binary tree
void preOrder(Node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
Node* convertSortedArrayToBalancedBST(int *arr, int start, int end) {
// Base Case
if (start > end) {
return NULL;
}
// find the middle element of the array
int mid = (start + end) / 2;
// the middle element forms the root of the balanced BST
Node *root = new Node(arr[mid]);
// elements to the left of mid forms the left subtree
root->left = convertSortedArrayToBalancedBST(arr, start, mid - 1);
// elements to the right of mid forms the right subtree
root->right = convertSortedArrayToBalancedBST(arr, mid + 1, end);
// return root
return root;
}
int main() {
// Example 1
int arr1[] = {1, 2, 3, 4, 5};
Node *root1 = convertSortedArrayToBalancedBST(arr1, 0, sizeof(arr1) / sizeof(arr1[0]) - 1);
preOrder(root1);
cout<<endl;
// Example 2
int arr2[] = {7, 11, 13, 20, 22, 41};
Node *root2 = convertSortedArrayToBalancedBST(arr2, 0, sizeof(arr2) / sizeof(arr2[0]) - 1);
preOrder(root2);
cout<<endl;
return 0;
}
3 1 2 4 5 13 7 11 22 20 41
