بدل کړئ BST ته د من ګیر ته


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon تورکاک ByteDance په روبل روغتيا Honeywell
د بائنری لټون ونه دوهم ونې ap He. ونې

ستونزه بیان

بشپړ ورکړل شو د بائنری لټون ونه، الګوریتم ولیکئ چې دا په A بدل کړئ لږ من، کوم چې د BST ته د Min Heap ته واړوئ. د من ګیرۍ باید داسې وي چې د نوډ په کی on اړخ کې باید ارزښتونه د دې نوډ په ښي اړخونو لږ وي.

بېلګه

ننوتۍ

بدل کړئ BST ته د من ګیر ته

Output

بدل کړئ BST ته د من ګیر ته

کچه امر: 6 7 13 9 12 18 23

الګوریتم د BST څخه د من ګیډۍ ته بدلولو لپاره

د بائنری لټون ونې کې داسې عناصر شامل دي چې د هغې 'په ترتیب ټروراسال عناصر په ترتیب شوي ب givesه ورکوي. د بی ایس ٹی مین من ته بدلولو لپاره موږ د بائنري لټون ونې په ترتیب ترتیب ټرورسل د مخه په ترتیب ټریورسل کې واړوو ، دا دی ، موږ د ونې ترتیب ټرورسال په یو صف کې ذخیره کوو او بیا نوډونه د پری ترتیب په فیشن کې ځای په ځای کوو. د سپارښتنې ترتیب سره.

دا به ډاډ ترلاسه کړي چې د بائنري لټون ونې یو من هپ ته واړوي او د من هپ ورکړل شوې ملکیت هم راضي کوي ، دا دی ، د نوډ د کی sub سب ونې ټول نوډونه د ښیې فرعي ونې د ټولو نوډونو څخه کوچني دي. د هغه ونې

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)

له هغه وخته چې موږ د ونې ترتیب او مخکې له مخکې ځړونې ترسره کړې چې یوازې O (N) وخت نیسي.

د ځای پیچلتیا = O (N)

دلته موږ د N عناصر ذخیره کوو ، پدې توګه د خطي خلا پیچلتیا ځای حل /.
چیرې چې N بشپړ د بائنري لټون په ونې کې د نوډونو مجموعه شمیره ده.

تشریح

پورتنۍ مثال کې ښودل شوي ونې ته پام وکړئ.

ګام 1
ونه په ترتیب ترتیب کې وباسئ او په صف کې یې زیرمه کړئ.
تیر [] = {6 ، 7 ، 9 ، 12 ، 13 ، 18 ، 23}

مرحله 2 & 3
ونه د مخکینۍ سپارښتنې په بverseه وګرځئ او د هر نوډ ارزښت په صف کې زیرمه شوي ارزښت سره ځای په ځای کړئ.

بدل کړئ BST ته د من ګیر ته

لکه څنګه چې موږ په ارقام کې لیدلی شو ، ونه د ورکړل شوي ملکیتونو پوره کولو سره په منۍ بدل شوی.

کوډ

د جاوا کوډ BST ته د من ګیر ته واړوئ

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 ته د من ګیر ته واړوئ

#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