Construir un árbol a partir de recorridos en orden Inorder y Level | conjunto 2

Dados los recorridos en orden y en orden de nivel de un árbol binario, construya el árbol binario. A continuación se muestra un ejemplo para ilustrar el problema.

Ejemplos: 

Input: Two arrays that represent Inorder
       and level order traversals of a 
       Binary Tree
in[]    = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};

Output: Construct the tree represented 
        by the two arrays.
        For the above two arrays, the 
        constructed tree is shown.

Hemos discutido una solución en la publicación a continuación que funciona en O (N ^ 3) 
Construya un árbol a partir de recorridos de orden Inorder y Level | Serie 1

Enfoque: El siguiente algoritmo usa la complejidad de tiempo O(N^2) para resolver el problema anterior usando la estructura de datos unordered_set en C++ (básicamente haciendo una tabla hash) para poner los valores del subárbol izquierdo de la raíz actual y más tarde y lo comprobaremos en complejidad O(1) para encontrar si el Node levelOrder actual es parte del subárbol izquierdo o no.
Si es parte del subárbol izquierdo, agregue una array lLevel para la izquierda; de lo contrario, agréguela a la array rLevel para el subárbol derecho.

A continuación se muestra la implementación con la idea anterior. 

/* program to construct tree using inorder
   and levelorder traversals */
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node */
struct Node
{
    int key;
    struct Node* left, *right;
};
 
Node* makeNode(int data){
    Node* newNode = new Node();
    newNode->key = data;
    newNode->right = newNode->right = NULL;
    return newNode;
}
 
// Function to build tree from given
// levelorder and inorder
Node* buildTree(int inorder[], int levelOrder[],
                int iStart, int iEnd, int n)
{
    if (n <= 0)
          return NULL;
 
    // First node of level order is root
    Node* root = makeNode(levelOrder[0]);
 
    // Search root in inorder
    int index = -1;
    for (int i=iStart; i<=iEnd; i++){
        if (levelOrder[0] == inorder[i]){
            index = i;
            break;
        }
    }
 
    // Insert all left nodes in hash table
    unordered_set<int> s;
    for (int i=iStart;i<index;i++)
        s.insert(inorder[i]);
     
    // Separate level order traversals
    // of left and right subtrees.
    int lLevel[s.size()];  // Left
    int rLevel[iEnd-iStart-s.size()]; // Right
    int li = 0, ri = 0;
    for (int i=1;i<n;i++) {
        if (s.find(levelOrder[i]) != s.end())
            lLevel[li++] = levelOrder[i];
        else
            rLevel[ri++] = levelOrder[i];       
    }
 
    // Recursively build left and right
    // subtrees and return root.
    root->left = buildTree(inorder, lLevel,
                 iStart, index-1, index-iStart);
    root->right = buildTree(inorder, rLevel,
                  index+1, iEnd, iEnd-index);
    return root;
 
}
 
/* Utility function to print inorder
traversal of binary tree */
void printInorder(Node* node)
{
    if (node == NULL)
       return;
    printInorder(node->left);
    cout << node->key << " ";
    printInorder(node->right);
}
 
// Driver Code
int main()
{
    int in[] = {4, 8, 10, 12, 14, 20, 22};
    int level[] = {20, 8, 22, 4, 12, 10, 14};
    int n = sizeof(in)/sizeof(in[0]);
    Node *root = buildTree(in, level, 0,
                           n - 1, n);
 
    /* Let us test the built tree by
     printing Inorder traversal */
    cout << "Inorder traversal of the "
            "constructed tree is \n";
    printInorder(root);
 
    return 0;
}

/*
 * program to construct tree using inorder
 * and levelorder traversals
 */
import java.util.HashSet;
class GFG
{
 
  /* A binary tree node */
  static class Node {
    int key;
    Node left, right;
  };
 
  static Node makeNode(int data) {
    Node newNode = new Node();
    newNode.key = data;
    newNode.right = newNode.right = null;
    return newNode;
  }
 
  // Function to build tree from given
  // levelorder and inorder
  static Node buildTree(int inorder[], int levelOrder[], int iStart, int iEnd, int n) {
    if (n <= 0)
      return null;
 
    // First node of level order is root
    Node root = makeNode(levelOrder[0]);
 
    // Search root in inorder
    int index = -1;
    for (int i = iStart; i <= iEnd; i++) {
      if (levelOrder[0] == inorder[i]) {
        index = i;
        break;
      }
    }
 
    // Insert all left nodes in hash table
    HashSet<Integer> s = new HashSet<>();
    for (int i = iStart; i < index; i++)
      s.add(inorder[i]);
 
    // Separate level order traversals
    // of left and right subtrees.
    int[] lLevel = new int[s.size()]; // Left
    int[] rLevel = new int[iEnd - iStart - s.size()]; // Right
    int li = 0, ri = 0;
    for (int i = 1; i < n; i++) {
      if (s.contains(levelOrder[i]))
        lLevel[li++] = levelOrder[i];
      else
        rLevel[ri++] = levelOrder[i];
    }
 
    // Recursively build left and right
    // subtrees and return root.
    root.left = buildTree(inorder, lLevel, iStart, index - 1, index - iStart);
    root.right = buildTree(inorder, rLevel, index + 1, iEnd, iEnd - index);
    return root;
 
  }
 
  /*
     * Utility function to print inorder
     * traversal of binary tree
     */
  static void printInorder(Node node) {
    if (node == null)
      return;
    printInorder(node.left);
    System.out.print(node.key + " ");
    printInorder(node.right);
  }
 
  // Driver Code
  public static void main(String[] args) {
 
    int in[] = { 4, 8, 10, 12, 14, 20, 22 };
    int level[] = { 20, 8, 22, 4, 12, 10, 14 };
    int n = in.length;
    Node root = buildTree(in, level, 0, n - 1, n);
 
    /*
         * Let us test the built tree by
         * printing Inorder traversal
         */
    System.out.println("Inorder traversal of the constructed tree is ");
    printInorder(root);
 
  }
}
 
// This code is contributed by sanjeev2552

<script>
    /*
     program to construct tree using inorder
     and levelorder traversals
     */
      
     /* A binary tree node */
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.key = data;
        }
    }
 
    function makeNode(data) {
      let newNode = new Node(data);
      return newNode;
    }
 
    // Function to build tree from given
    // levelorder and inorder
    function buildTree(inorder, levelOrder, iStart, iEnd, n) {
      if (n <= 0)
        return null;
 
      // First node of level order is root
      let root = makeNode(levelOrder[0]);
 
      // Search root in inorder
      let index = -1;
      for (let i = iStart; i <= iEnd; i++) {
        if (levelOrder[0] == inorder[i]) {
          index = i;
          break;
        }
      }
 
      // Insert all left nodes in hash table
      let s = new Set();
      for (let i = iStart; i < index; i++)
        s.add(inorder[i]);
 
      // Separate level order traversals
      // of left and right subtrees.
      let lLevel = new Array(s.size); // Left
      let rLevel = new Array(iEnd - iStart - s.size); // Right
      let li = 0, ri = 0;
      for (let i = 1; i < n; i++) {
        if (s.has(levelOrder[i]))
          lLevel[li++] = levelOrder[i];
        else
          rLevel[ri++] = levelOrder[i];
      }
 
      // Recursively build left and right
      // subtrees and return root.
      root.left = buildTree(inorder, lLevel, iStart, index - 1,
      index - iStart);
      root.right = buildTree(inorder, rLevel, index + 1, iEnd,
      iEnd - index);
      return root;
 
    }
 
    /*
       * Utility function to print inorder
       * traversal of binary tree
       */
    function printInorder(node) {
      if (node == null)
        return;
      printInorder(node.left);
      document.write(node.key + " ");
      printInorder(node.right);
    }
     
    let In = [ 4, 8, 10, 12, 14, 20, 22 ];
    let level = [ 20, 8, 22, 4, 12, 10, 14 ];
    let n = In.length;
    let root = buildTree(In, level, 0, n - 1, n);
  
    /*
         * Let us test the built tree by
         * printing Inorder traversal
         */
    document.write("Inorder traversal of the constructed tree is " +
    "</br>");
    printInorder(root);
 
</script>

Inorder traversal of the constructed tree is 
4 8 10 12 14 20 22 

Complejidad del tiempo: O(N^2)

Optimización: sin arrays transversales de orden de nivel separadas de subárboles izquierdo y derecho.

Enfoque: Uso de Hashing.

Use un HashMap para almacenar los índices de recorrido de orden de nivel. En el rango de inicio y fin desde el orden, busque el elemento con el menor índice del mapa de orden de nivel. Cree subárboles izquierdo y derecho recursivamente.

index -> the least index
for left subtree: start to index-1
for right subtree: index+1 to end

Implementación:

import java.util.HashMap;
 
//class Node
class Node{
    int data;
    Node left,right;
    Node(int data){
        this.data = data;
        left = right = null;
    }
}
 
public class ConstructTree {
     
    //hashmap to store the indices of levelorder array
    HashMap<Integer,Integer> map = new HashMap<>();
     
    //function to construct hashmap
    void constructMap(int level[]) {
        for(int i=0;i<level.length;i++)
            map.put(level[i], i);
    }
     
    //function to construct binary tree from inorder and levelorder
    Node construct(int in[],int start,int end) {
        //if start is greater than end return null
        if(start > end)
            return null;
         
        int min_index = start;
         
        //In the range of start & end from inorder, search the element
        //with least index from level order map
        for(int i=start+1;i<=end;i++) {
            int temp = in[i];
            //if current element from inorder have least index in
            //levelorder map, update min_index
            if(map.get(in[min_index]) > map.get(temp))
                min_index = i;
        }
         
        //create a node with current element
        Node root = new Node(in[min_index]);
         
        //if start is equal to end, then return root
        if(start == end)
            return root;
         
        //construct left and right subtrees
        root.left = construct(in,start,min_index-1);
        root.right = construct(in,min_index+1,end);
         
        return root;
    }
     
    //function to print inorder
    void printInorder(Node node) {
        if (node == null)
          return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
      }
     
    //Driver function
    public static void main(String[] args) {
        ConstructTree tree = new ConstructTree();
         
        int in[]    = {4, 8, 10, 12, 14, 20, 22};
        int level[] = {20, 8, 22, 4, 12, 10, 14};
         
        //function calls
        tree.constructMap(level);
        int n = level.length;
        Node root = tree.construct(in, 0, n-1);
        tree.printInorder(root);
    }
}
 
//This method is contributed by Likhita AVL

4 8 10 12 14 20 22 

Complejidad de tiempo: O(n^2).