Construya un árbol binario perfecto con la altura dada

Dado un número entero N , la tarea es generar un árbol binario perfecto con altura N tal que cada Node tenga un valor que sea igual a su profundidad. Devuelve el recorrido en orden del árbol binario generado.

Un árbol binario perfecto es un tipo de árbol binario en el que cada Node interno tiene exactamente dos Nodes secundarios y todos los Nodes hoja están al mismo nivel. 

Ejemplos:

Entrada: N = 2
Salida: 2 1 2 0 2 1 2
Explicación: La estructura del árbol es la siguiente

Árbol binario perfecto con altura 2

Entrada: N = 1
Salida: 1 0 1

Enfoque: el problema se puede resolver utilizando un recorrido de orden de nivel basado en la siguiente observación:

Como hay un requisito para llenar cada Node con el mismo valor que su profundidad, use el recorrido de orden de nivel. En cada paso, rellene un nivel total y marque todos los Nodes con el mismo valor que la profundidad.

Siga los pasos que se mencionan a continuación para implementar el enfoque:

• Inicia una variable para almacenar la profundidad del nivel actual.
• Inicie una cola para almacenar el Node de cada nivel y realice el recorrido del orden de niveles.
• En cada iteración obtenga todos los Nodes en ese nivel y continúe lo siguiente hasta que la profundidad sea N:
  • Aumenta la profundidad en 1.
  • Pop los Nodes en el nivel actual.
  • Genere los Nodes secundarios para cada Node.
  • Agregue los nuevos Nodes secundarios para su posterior procesamiento.
• Una vez completado el recorrido, se prepara el árbol.
• Imprime el recorrido en orden del árbol.

A continuación se muestra la implementación del enfoque anterior.

// Java code to implement the approach
 
import java.util.*;
 
// Class to hold tree node data
// and left, right children
class TreeNode {
    public long val;
    public TreeNode left;
    public TreeNode right;
 
    public TreeNode(long x)
    {
        val = x;
        left = null;
        right = null;
    }
}
 
// Class to create the perfect binary tree
class BinaryTree {
 
    // Method to construct a binary tree
    public static TreeNode perfectBinaryTree(int depth)
    {
        // Return root with 0 as val if height is 0
        if (depth == 0)
            return new TreeNode(0);
 
        // Initiate queue to store
        // the nodes on each level
        Queue<TreeNode> queue
            = new LinkedList<>();
 
        // Create a root node with value 0
        long i = 0;
        TreeNode root = new TreeNode(i);
 
        // Add the root node to the queue
        // for futher processing
        queue.add(root);
 
        // Iterate through the queue till its empty
        while (!queue.isEmpty()) {
 
            // Check the size of the queue to iterate
            // through each node on the same level
            int size = queue.size();
 
            // Increment the value of node
            // upon each level
            i++;
 
            // Break the loop if the value of the node
            // reaches given depth
            // else process the node in the queue
            if (i > depth) {
                break;
            }
            else {
                // Add the left and right child
                // for the node in the queue and
                // add those newly created child nodes
                // to the queue.
                for (int j = 0; j < size; j++) {
                    TreeNode node = queue.remove();
                    node.left = new TreeNode(i);
                    node.right = new TreeNode(i);
 
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
        }
 
        // Return the root of the tree
        return root;
    }
 
    // Inorder traversal of the tree (Left Root Right)
    public static void inOrderTraversal(TreeNode node)
    {
        if (node == null)
            return;
        inOrderTraversal(node.left);
        System.out.print(node.val + " ");
        inOrderTraversal(node.right);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 2;
 
        // Function call to build the tree
        TreeNode binaryTreeRoot
            = perfectBinaryTree(N);
 
        // Function call to print the tree
        inOrderTraversal(binaryTreeRoot);
    }
}

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
// Class to hold tree node data
// and left, right children
public class TreeNode {
  public long val;
  public TreeNode left;
  public TreeNode right;
 
  public TreeNode(long x) {
    val = x;
    left = null;
    right = null;
  }
}
 
// Class to create the perfect binary tree
public class BinaryTree {
 
  // Method to construct a binary tree
  public static TreeNode perfectBinaryTree(int depth) {
    // Return root with 0 as val if height is 0
    if (depth == 0)
      return new TreeNode(0);
 
    // Initiate queue to store
    // the nodes on each level
    Queue<TreeNode> queue = new Queue<TreeNode>();
 
    // Create a root node with value 0
    long i = 0;
    TreeNode root = new TreeNode(i);
 
    // Add the root node to the queue
    // for futher processing
    queue.Enqueue(root);
 
    // Iterate through the queue till its empty
    while (queue.Count!=0) {
 
      // Check the size of the queue to iterate
      // through each node on the same level
      int size = queue.Count;
 
      // Increment the value of node
      // upon each level
      i++;
 
      // Break the loop if the value of the node
      // reaches given depth
      // else process the node in the queue
      if (i > depth) {
        break;
      } else {
        // Add the left and right child
        // for the node in the queue and
        // add those newly created child nodes
        // to the queue.
        for (int j = 0; j < size; j++) {
          TreeNode node = queue.Dequeue();
          node.left = new TreeNode(i);
          node.right = new TreeNode(i);
 
          queue.Enqueue(node.left);
          queue.Enqueue(node.right);
        }
      }
    }
 
    // Return the root of the tree
    return root;
  }
 
  // Inorder traversal of the tree (Left Root Right)
  public static void inOrderTraversal(TreeNode node) {
    if (node == null)
      return;
    inOrderTraversal(node.left);
    Console.Write(node.val + " ");
    inOrderTraversal(node.right);
  }
 
  // Driver code
  public static void Main(String[] args) {
    int N = 2;
 
    // Function call to build the tree
    TreeNode binaryTreeRoot = perfectBinaryTree(N);
 
    // Function call to print the tree
    inOrderTraversal(binaryTreeRoot);
  }
}
 
// This code is contributed by shikhasingrajput

2 1 2 0 2 1 2 

Complejidad de Tiempo: O(2 ^N )
Espacio Auxiliar: O(2 ^N )