시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
완전한 주어진 이진 검색 트리, 알고리즘을 작성하여 최소 힙, BST를 Min Heap으로 변환합니다. 최소 힙은 노드의 왼쪽에있는 값이 해당 노드의 오른쪽에있는 값보다 작아야합니다.
예
입력
산출
레벨 오더 : 6 7 13 9 12 18 23
BST를 최소 힙으로 변환하는 알고리즘
이진 검색 트리에는 순회 순회가 요소를 정렬 된 형식으로 제공하는 요소가 포함되어 있습니다. BST를 Min Heap으로 변환하기 위해 사전 주문 순회에서 이진 검색 트리의 순회 순회를 변환합니다. 즉, 트리의 순회 순회를 배열에 저장 한 다음 사전 주문 방식으로 노드를 교체합니다. 순서대로 출력합니다.
이렇게하면 이진 검색 트리가 최소 힙으로 변환되고 최소 힙도 주어진 속성을 충족합니다. 즉, 노드의 왼쪽 하위 트리에있는 모든 노드가 오른쪽 하위 트리의 모든 노드보다 작습니다. 그 나무의.
1. Traverse the BST in in-order traversal and store the traversal in an array or a list. 2. This time traverse the Binary Search Tree in pre-order form. 3. Replace every node with the corresponding value stored in the array or list.
시간 복잡성 = 의 위에)
우리는 O (N) 시간 만 걸리는 트리의 순서 및 순서 순회를 수행했기 때문에.
공간 복잡성 = 의 위에)
여기에 n 개의 요소를 저장하고 있으므로 선형 공간 복잡성 공간 솔루션 /.
여기서 N은 전체 이진 검색 트리의 총 노드 수입니다.
설명
위의 예에 표시된 트리를 고려하십시오.
1단계
순서대로 트리를 가로 질러 배열에 저장합니다.
arr [] = {6, 7, 9, 12, 13, 18, 23}
2 단계 및 3 단계
사전 주문 양식으로 트리를 가로 질러 모든 노드의 값을 배열에 저장된 해당 값으로 바꿉니다.
그림에서 볼 수 있듯이 트리는 주어진 속성을 만족하는 Min Heap으로 변환됩니다.
암호
BST를 최소 힙으로 변환하는 Java 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class ConvertBSTToMinHeap {
// 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 level order traversal of binary tree
private static void levelOrder(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
System.out.print(curr.data + " ");
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
}
// function to store the inorder traversal of tree in a list
private static void storeInOrder(Node root, ArrayList<Integer> inOrder) {
if (root != null) {
storeInOrder(root.left, inOrder);
inOrder.add(root.data);
storeInOrder(root.right, inOrder);
}
}
// function to replace the inorder traversal with pre-order traversal
private static void replaceInOrderWithPreOrder(Node root, ArrayList<Integer> inOrder) {
if (root != null) {
root.data = inOrder.get(0);
inOrder.remove(0);
replaceInOrderWithPreOrder(root.left, inOrder);
replaceInOrderWithPreOrder(root.right, inOrder);
}
}
private static void convertToMinHeap(Node root) {
ArrayList<Integer> inOrderTraversal = new ArrayList<>();
// store the in order traversal of the tree in a list
storeInOrder(root, inOrderTraversal);
// replace the pre order traversal with in order traversal
replaceInOrderWithPreOrder(root, inOrderTraversal);
}
public static void main(String[] args) {
// Example Tree
Node root = new Node(12);
root.left = new Node(7);
root.right = new Node(18);
root.left.left = new Node(6);
root.left.right = new Node(9);
root.right.left = new Node(13);
root.right.right = new Node(23);
convertToMinHeap(root);
levelOrder(root);
System.out.println();
}
}
6 7 13 9 12 18 23
BST를 최소 힙으로 변환하는 C ++ 코드
#include <bits/stdc++.h>
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 level order traversal of binary tree
void levelOrder(Node *root) {
if (root == NULL) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node *curr = q.front();
q.pop();
cout<<curr->data<<" ";
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
}
// function to store the inorder traversal of tree in a list
void storeInOrder(Node *root, vector<int> &inOrderTraversal) {
if (root != NULL) {
storeInOrder(root->left, inOrderTraversal);
inOrderTraversal.push_back(root->data);
storeInOrder(root->right, inOrderTraversal);
}
}
// function to replace the inorder traversal with pre-order traversal
void replaceInOrderWithPreOrder(Node *root, vector<int> &inOrderTraversal) {
if (root != NULL) {
root->data = inOrderTraversal[0];
inOrderTraversal.erase(inOrderTraversal.begin());
replaceInOrderWithPreOrder(root->left, inOrderTraversal);
replaceInOrderWithPreOrder(root->right, inOrderTraversal);
}
}
void convertToMinHeap(Node *root) {
std::vector<int> inOrderTraversal;
// store the in order traversal of the tree in a list
storeInOrder(root, inOrderTraversal);
// replace the pre order traversal with in order traversal
replaceInOrderWithPreOrder(root, inOrderTraversal);
}
int main() {
// Example Tree
Node *root = new Node(12);
root->left = new Node(7);
root->right = new Node(18);
root->left->left = new Node(6);
root->left->right = new Node(9);
root->right->left = new Node(13);
root->right->right = new Node(23);
convertToMinHeap(root);
levelOrder(root);
cout<<endl;
return 0;
}
6 7 13 9 12 18 23
