Построить двоичное дерево из заданного представления родительского массива


Сложный уровень средний
Часто спрашивают в Амазонка Microsoft Snapdeal
массив Двоичное дерево дерево

Задача «Построить двоичное дерево из заданного представления родительского массива» утверждает, что вам дан массив. Этот входной массив представляет собой двоичное дерево. Теперь вам нужно построить двоичное дерево на основе этого входного массива. В массиве хранится индекс родительского узла по каждому индексу.

Пример

Построить двоичное дерево из заданного представления родительского массива

Inorder Traversal: 3 1 0 4 2 5

Подход

Задача просит нас построить двоичное дерево из заданного родителя. массив представление. Родительский массив хранит индекс родительского узла в каждом индексе массива. Теперь вам нужно построить двоичное дерево, используя этот массив. Значение -1 во входном массиве обозначает корневой узел в дерево.

Наивный подход - продолжать создавать новые узлы. Когда мы создаем эти узлы, мы всегда создаем узлы в порядке их уровня в двоичном дереве. Например, сначала мы создаем root, затем его дочерние элементы и так далее. затем, когда мы создаем узлы, мы присоединяем узлы к дереву с помощью модификации указателей. Но этот подход неэффективен, так как мы будем перемещаться по дереву, чтобы найти родителя текущего созданного узла.

Лучшее и эффективное решение - отслеживать уже созданные узлы. Таким образом, нам не нужно искать родителя текущего узла. Это решение немного другое. Здесь мы сначала проверим, создан ли родительский узел. Если он был создан, то ничего страшного. В противном случае мы рекурсивно создаем все родительские узлы, а затем создаем дочерний узел. Таким образом, мы также продолжаем прикреплять дочерние узлы с модификацией указателя.

Код:

Код C ++ для построения двоичного дерева из заданного представления родительского массива

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void createNode(int a[], int i, node* created[]){
    // if current node is root
    if(a[i] == -1){
        node* cur = new node();
        cur->data = i;
        created[i] = cur;
        return;
    }

    // if the parent node has not been created
    if(created[a[i]] == NULL)
        createNode(a, a[i], created);

    // create current node
    node* cur = new node();
    cur->data = i;
    // insert the node value in created array
    created[i] = cur;

    // if left child of parent is null
    // attach current node as its left child
    if(created[a[i]]->left == NULL)
        created[a[i]]->left = cur;
    // else attach it as right child
    else if(created[a[i]]->right == NULL)
        created[a[i]]->right = cur;
}

int main()
{
  int a[] = {-1, 0, 0, 1, 2, 2};
  int n = (sizeof a) / (sizeof a[0]);
  node* created[n];
  memset(created, NULL, sizeof created);
  node* root = NULL;
  for(int i=0;i<n;i++){
        // if node has not been created
        if(created[i] == NULL)
            createNode(a, i, created);
        // store the root node
        if(a[i] == -1)
            root = created[i];
  }
  // print the inorder traversal of the root
  inorder(root);
}
3 1 0 4 2 5

Код Java для построения двоичного дерева из заданного представления родительского массива

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  static void createNode(int a[], int i, node created[]){
      // if current node is root
      if(a[i] == -1){
          node cur = new node();
          cur.data = i;
          created[i] = cur;
          return;
      }

      // if the parent node has not been created
      if(created[a[i]] == null)
          createNode(a, a[i], created);

      // create current node
      node cur = new node();
      cur.data = i;
      // insert the node value in created array
      created[i] = cur;

      // if left child of parent is null
      // attach current node as its left child
      if(created[a[i]].left == null)
          created[a[i]].left = cur;
      // else attach it as right child
      else if(created[a[i]].right == null)
          created[a[i]].right = cur;
  }

  public static void main(String[] args)
  {
    int a[] = {-1, 0, 0, 1, 2, 2};
    int n = 6;
    node created[] = new node[n];
    node root = null;
    for(int i=0;i<n;i++){
          // if node has not been created
          if(created[i] == null)
              createNode(a, i, created);
          // store the root node
          if(a[i] == -1)
              root = created[i];
    }
    // print the inorder traversal of the root
    inorder(root);
  }
}
3 1 0 4 2 5

Анализ сложности

Сложность времени

НА), потому что даже если мы используем рекурсию. Если узел создан, мы больше никогда не создадим тот же узел. Таким образом, срок является линейным.

Космическая сложность

НА), потому что мы создали массив узлов, чтобы проверить, создан ли узел или нет. Таким образом, сложность пространства также линейна.