Пабудуйце BST па зададзеным абходным парадку ўзроўню


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка яблык GE Healthcare MetLife Microsoft UHG Optum Скуголіць
Двайковае дрэва пошуку Двайковае дрэва Шырыня Першы пошук дрэва Абход дрэва

Улічваючы абход узроўневага парадку двайковага дрэва пошуку, напішыце алгарытм пабудовы двайковага дрэва пошуку альбо BST з ІТС з зададзеным узроўнем парадку.

Прыклад

уваход
levelOrder [] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31}
выхад

Пабудуйце BST па зададзеным абходным парадку ўзроўню

У парадку: 5 8 9 12 15 18 20 22 25 31

уваход
levelOrder [] = {4, 2, 5, 1, 3, 6}
выхад

Пабудуйце BST па зададзеным абходным парадку ўзроўню

У парадку: 1 2 3 4 5 6

Алгарытм пабудовы BST з развароту парадку ўзроўню

Першы элемент у абходцы парадку ўзроўню заўсёды ўтварае корань бінарнага пошуку дрэва. Наступнае значэнне можа ўтвараць левы вузел ці правы вузел у залежнасці ад яго значэння.

Калі наступны вузел менш кораня, чым ён будзе ўстаўлены злева ад кораня, у адваротным выпадку ён будзе ўстаўлены справа.
Ідэя заключаецца ў наступным: калі корань BST роўны нулю, утвараючы бягучы элемент менш кораня, устаўце яго ў адпаведную пазіцыю ў левым паддрэве кораня, у адваротным выпадку ўстаўце неадпаведную пазіцыю ў правым паддрэве кораня.

  1. Ініцыялізуйце корань BST як нуль. Калі ў абходцы парадку ўзроўню няма элементаў, вярніце корань.
  2. Для кожнага элемента ў масіве levelOrder паўторыце крокі 3, 4 і 5.
  3. Калі корань нулявы, зрабіце бягучы элемент каранёвым.
  4. У адваротным выпадку, калі бягучы элемент менш кораня, перайдзіце да кроку 3, корань становіцца root.left і элемент застаецца ранейшым.
  5. У адваротным выпадку, калі бягучы элемент большы за корань, перайдзіце да кроку 3, корань становіцца root.right і элемент застаецца ранейшым.
  6. Вярнуць корань.

Код JAVA для пабудовы BST з абходкі парадку ўзроўню

public class ConstructBSTFromItsGivenLevelOrderTraversal {
    // 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 in order traversal of a binary tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

Код C ++ для пабудовы BST з абходу парадку ўзроўню

#include <iostream> 
#include<vector> 
#include<queue> 
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 the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

Аналіз складанасці

Складанасць часу = О (н2)
Складанасць прасторы = Аб (п), з-за рэкурсіі
дзе n - агульная колькасць элементаў у парадку ўзроўню масіў.

Даведка1     спасылка2