แปลง BST เป็น Min Heap


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน แบล็ค ByteDance GE Healthcare Honeywell
ต้นไม้ค้นหาแบบไบนารี ต้นไม้ไบนารี กอง ต้นไม้

คำชี้แจงปัญหา

ได้รับที่สมบูรณ์ ต้นไม้ค้นหาแบบไบนารีเขียนอัลกอริทึมเพื่อแปลงเป็นไฟล์ มินฮีปซึ่งก็คือการแปลง BST เป็น Min Heap Min Heap ควรเป็นค่าที่ค่าทางซ้ายของโหนดต้องน้อยกว่าค่าทางขวาของโหนดนั้น

ตัวอย่าง

อินพุต

แปลง BST เป็น Min Heap

เอาท์พุต

แปลง BST เป็น Min Heap

ลำดับระดับ: 6 7 13 9 12 18 23

อัลกอริทึมในการแปลง BST เป็น Min Heap

แผนภูมิการค้นหาแบบไบนารีมีองค์ประกอบที่ 'การส่งผ่านตามลำดับทำให้องค์ประกอบในรูปแบบที่เรียงลำดับ ในการแปลง BST เป็น Min Heap เราจะแปลงการส่งผ่านตามลำดับของ Binary Search Tree ในการสั่งซื้อล่วงหน้านั่นคือเราจัดเก็บการส่งผ่านตามลำดับของทรีในอาร์เรย์แล้วแทนที่โหนดตามลำดับ ด้วยเอาต์พุตตามลำดับ

สิ่งนี้จะช่วยให้มั่นใจได้ว่า Binary Search Tree แปลงเป็น Min Heap และ 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

ดังที่เราเห็นในรูปต้นไม้ถูกแปลงเป็น Min Heap ตามคุณสมบัติที่กำหนด

รหัส

Java Code เพื่อแปลง BST เป็น Min Heap

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

รหัส C ++ เพื่อแปลง BST เป็น Min Heap

#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