BSTを最小ヒープに変換する


難易度 ハード
よく聞かれる Amazon (アマゾン) ブラックロック ByteDance GEヘルスケア ハニーウェル
二分探索木 二分木 ヒープ

問題文

完全に与えられた 二分探索木、それをに変換するアルゴリズムを書く 最小ヒープ、これはBSTを最小ヒープに変換することです。 最小ヒープは、ノードの左側の値がそのノードの右側の値よりも小さくなければならないようなものでなければなりません。

入力

BSTを最小ヒープに変換する

出力

BSTを最小ヒープに変換する

レベル順:6 7 13 9 12 18 23

BSTを最小ヒープに変換するアルゴリズム

二分探索木には、その順序どおりの走査が要素をソートされた形式で提供するような要素が含まれています。 BSTを最小ヒープに変換するために、バイナリ検索ツリーのインオーダートラバーサルをプレオーダートラバーサルに変換します。つまり、ツリーのインオーダートラバーサルを配列に格納してから、ノードをプレオーダー方式で置き換えます。順序どおりの出力で。

これにより、バイナリ検索ツリーが最小ヒープに変換され、最小ヒープが指定されたプロパティを満たします。つまり、ノードの左側のサブツリーのすべてのノードが、右側のサブツリーのすべてのノードよりも小さくなります。その木の。

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を最小ヒープに変換する

図からわかるように、ツリーは指定されたプロパティを満たす最小ヒープに変換されます。

コード

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