배열을 사용하지 않고 BST를 최소 힙으로 변환

난이도 하드
자주 묻는 질문 아마존 시스코 Microsoft SAP 연구소
이진 검색 트리 이진 트리 나무조회수 64

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

문제 정책

"배열을 사용하지 않고 BST를 최소 힙으로 변환"문제는 BST (이진 검색 트리)를 받았으며이를 최소 힙으로 변환해야한다는 문제를 나타냅니다. 최소 힙은 이진 검색 트리의 모든 요소를 ​​포함해야합니다. 알고리즘은 선형 시간 복잡도로 실행되어야합니다.

입력

배열을 사용하지 않고 BST를 최소 힙으로 변환

산출

배열을 사용하지 않고 BST를 최소 힙으로 변환

배열을 사용하지 않고 BST를 최소 힙으로 변환하는 방법

순진한 접근

“배열을 사용하지 않고 BST를 Min-Heap으로 변환”문제는 먼저 순서대로 순회를 저장하면 해결할 수 있습니다. 이진 검색 트리. 그리고 순회 순회를 찾은 후, 우리는 min-heap (부모보다 작은 하위 트리의 모든 하위를 갖는 완전한 바이너리 트리)를 만들기 시작합니다. 그렇다면 최소 힙을 어떻게 만들까요? 우리는 최소 힙 완전한 이진 트리 속성을 보장하는 레벨 순서 순회에 요소를 레벨 배치하여. 그리고 순회 순회가 있기 때문에 min-heap의 속성이 충족된다는 것을 확신합니다 (부모가 두 자식보다 작음). 그러나이를 위해서는 순회 순회를 저장해야합니다.

효율적인 접근

이진 검색 트리를 연결 목록으로 먼저 변환하면 O (1) 공간에서이 문제를 해결할 수 있습니다. 연결 목록에는 정렬 된 순서 여야한다는 조건도 있습니다. 이를 위해 먼저 오른쪽 하위 트리를 탐색 한 다음 왼쪽 하위 트리를 탐색합니다. 연결 목록의 시작 부분에 노드를 삽입하기 때문입니다. 이렇게하면 연결된 목록이 정렬 된 상태로 유지됩니다. 일단 정렬 된 연결 목록이 있습니다. 완전한 이진 트리 속성이 충족되도록 노드의 왼쪽 및 오른쪽 포인터를 재정렬합니다. 순진한 접근 방식에서했던 것처럼, 우리는 최소 힙을 만들기 위해 레벨 순서 순회를 사용했습니다. 여기서도 같은 것을 사용할 것입니다.

암호

배열을 사용하지 않고 BST를 최소 힙으로 변환하는 C ++ 코드

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

struct node{
    int data;
    node* left;
    node* right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// prints the level order traversal of the tree
void levelOrderTraversal(node *root)
{
  if (root == NULL) return;
    queue<node*> q;
    q.push(root);
  while(!q.empty()){
        int qSize = q.size();
        while(qSize--){
            node* nodeAtFront = q.front();
            q.pop();
            if(nodeAtFront->left)
                q.push(nodeAtFront->left);
            if(nodeAtFront->right)
                q.push(nodeAtFront->right);
            cout<<nodeAtFront->data<<" ";
        }
        cout<<endl;
  }
}

void convertBSTToLinkedList(node* root, node* &head_ref)
{
    if(!root)
        return;

  //first convert right subtree into linked list
  convertBSTToLinkedList(root->right, head_ref);
  // insert root into the linked list
  root->right = head_ref;
  //if head pointer exists, then point left pointer to NULL
  if(head_ref)
        head_ref->left = NULL;
    // now head of linked list is current root
    head_ref = root;
    // convert left subtrree recursively
  convertBSTToLinkedList(root->left, head_ref);
}

void convertLinkedListToMinHeap(node* &root, node* head)
{
  // Base Case
  if(!head)
    return;

    //traverse over the linked list in level order traversal fashion
  queue<node*> q;
    //first node of min heap will be smallest element
    //i.e. first element of inorder traversal
    root = head;
    // point head to next node
    head = head->right;
    // left is already null
    root->right = NULL;
    // insert into queue
    q.push(root);
  while(head)
  {
      node* nodeAtFront = q.front();
      q.pop();
      // now remove one node from linked list and make left child
      // if there are more nodes make a right child
      // push them into queue
      node* leftNode = head;
      head = head->right;
      leftNode->right = NULL;
      nodeAtFront->left = leftNode;
      q.push(leftNode);
      // similarly do the same for right child if it exists
      if(head){
            node* rightNode = head;
            head = head->right;
            rightNode->right = NULL;
            nodeAtFront->right = rightNode;
            q.push(rightNode);
      }
  }
}

// Function to convert BST into a Min-Heap
// without using any extra space
node* BSTToMinHeap(node* &root)
{
  // head of Linked List
  node *head = NULL;
  // get converted linked list
  convertBSTToLinkedList(root, head);
  // now set the root for min heap
  root = NULL;
  // convert the linked list into min heap
  convertLinkedListToMinHeap(root, head);
}

int main()
{

  node* root = create(5);
  root->left = create(4);
  root->right = create(6);
  root->left->left = create(2);
  root->left->right = create(3);

  BSTToMinHeap(root);

        levelOrderTraversal(root);

  return 0;
}
2
4 3
5 6

배열을 사용하지 않고 BST를 최소 힙으로 변환하는 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }
 
  static void levelOrderTraversal(node root)
  {
    if (root == null) return;
      Queue<node> q = new LinkedList<>();
      q.add(root);
    while(!q.isEmpty()){
          int qSize = q.size();
          while(qSize-- > 0){
              node nodeAtFront = q.peek();
              q.remove();
              if(nodeAtFront.left != null)
                  q.add(nodeAtFront.left);
              if(nodeAtFront.right != null)
                  q.add(nodeAtFront.right);
              System.out.print(nodeAtFront.data+" ");
          }
          System.out.println();
    }
  }
  
  static node convertBSTToLinkedList(node root, node head_ref)
  {
      if(root == null)
          return head_ref;
  
    //first convert right subtree into linked list
    head_ref = convertBSTToLinkedList(root.right, head_ref);
    // insert root into the linked list
    root.right = head_ref;
    //if head pointer exists, then point left pointer to NULL
    if(head_ref != null)
          head_ref.left = null;
      // now head of linked list is current root
      head_ref = root;
      // convert left subtrree recursively
    head_ref = convertBSTToLinkedList(root.left, head_ref);
    
    return head_ref;
  }
  
  static node convertLinkedListToMinHeap(node root, node head)
  {
    // Base Case
    if(head == null)
      return null;
  
      //traverse over the linked list in level order traversal fashion
    Queue<node> q = new LinkedList<>();
      //first node of min heap will be smallest element
      //i.e. first element of inorder traversal
      root = head;
      // point head to next node
      head = head.right;
      // left is already null
      root.right = null;
      // insert into queue
      q.add(root);
    while(head != null)
    {
        node nodeAtFront = q.peek();
        q.remove();
        // now remove one node from linked list and make left child
        // if there are more nodes make a right child
        // push them into queue
        node leftNode = head;
        head = head.right;
        leftNode.right = null;
        nodeAtFront.left = leftNode;
        q.add(leftNode);
        // similarly do the same for right child if it exists
        if(head != null){
              node rightNode = head;
              head = head.right;
              rightNode.right = null;
              nodeAtFront.right = rightNode;
              q.add(rightNode);
        }
    }
    return root;
  }
  
  // Function to convert BST into a Min-Heap
  // without using any extra space
  static node BSTToMinHeap(node root)
  {
    // head of Linked List
    node head = null;
    // get converted linked list
    head = convertBSTToLinkedList(root, head);
    // now set the root for min heap
    root = null;
    // convert the linked list into min heap
    root = convertLinkedListToMinHeap(root, head);
    return root;
  }
  
  public static void main(String[] args)
  {
  
    node root = create(5);
    root.left = create(4);
    root.right = create(6);
    root.left.left = create(2);
    root.left.right = create(3);
  
    root = BSTToMinHeap(root);
  
      levelOrderTraversal(root);
  }

}
2 
4 3 
5 6 

복잡성 분석

시간 복잡성

의 위에), 먼저 트리를 연결 목록으로 변환 한 다음 레벨 순서 순회를 식별했기 때문입니다. 라이너 시간 복잡 작업 인 두 pf. 따라서 선형 시간 복잡도가 달성됩니다.

공간 복잡성

O (로그 N), 단일 레벨에 자식을 저장하기 위해 큐를 사용했기 때문입니다. 여기에는 대수 공간 복잡성이 필요합니다. 그러나 알고리즘 자체는 제자리에서 작동합니다.

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