BST를 최소 힙으로 변환

난이도 하드
자주 묻는 질문 아마존 BlackRock ByteDance GE 헬스 케어 하니웰
이진 검색 트리 이진 트리 더미 나무조회수 73

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

문제 정책

완전한 주어진 이진 검색 트리, 알고리즘을 작성하여 최소 힙, BST를 Min Heap으로 변환합니다. 최소 힙은 노드의 왼쪽에있는 값이 해당 노드의 오른쪽에있는 값보다 작아야합니다.

입력

BST를 최소 힙으로 변환

산출

BST를 최소 힙으로 변환

레벨 오더 : 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 단계
사전 주문 양식으로 트리를 가로 질러 모든 노드의 값을 배열에 저장된 해당 값으로 바꿉니다.

BST를 최소 힙으로 변환

그림에서 볼 수 있듯이 트리는 주어진 속성을 만족하는 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
균열 시스템 설계 인터뷰
Translate »