Imprima y elimine los Nodes de hoja del árbol binario dado en cada iteración

Dado un árbol binario, la tarea es:

• Imprima todos los Nodes hoja y luego elimínelos todos. 
• Repite este proceso hasta que el árbol se vacíe.

Ejemplos:

Entrada:        
              1
           /. \
        2 3
    / \   
 4 5      
Salida: 
Iteración 1: 4 5 3
Iteración 2: 2
Iteración 3: 1
Explicación: Los Nodes de hoja inicialmente eran 4, 5 y 3.
Cuando se eliminaron, solo el Node sin hijo es 2.
Entonces, el el Node hoja es 2. Después de eliminar 2, 1 es el único Node del árbol.
Entonces 1 se elimina en la tercera y última iteración.

Entrada:    
           1
         / 
       2
     /
   3               

Salida: 
Iteración 1: 3
Iteración 2: 2
Iteración 3: 1 

Enfoque ingenuo: este problema se puede resolver utilizando cualquier algoritmo transversal varias veces y en cada iteración simplemente imprima y elimine todos los Nodes de hoja. La referencia para este enfoque se puede encontrar aquí . 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea para resolver el problema de manera eficiente es la siguiente:

En lugar de hacer el recorrido varias veces, simplemente recorra solo una vez y al mismo tiempo calcule la profundidad de cada Node. 
Luego ordene los Nodes según la profundidad y obtendrá los Nodes de la primera hoja en la profundidad 0, los Nodes de la segunda iteración en la profundidad 1 y así sucesivamente.

Siga los pasos para resolver el problema:

• Atraviese el árbol recursivamente usando DFS .
• Para cualquier Node: 
  • Encuentre la profundidad del subárbol izquierdo. 
  • Encuentre la profundidad del subárbol correcto.  
  • Profundidad del Node = max(leftSubtreeDepth, rightSubtreeDepth) +1
• Almacene el valor del Node en un mapa según la profundidad (siendo la profundidad la clave y el valor del Node como un elemento en el vector)

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

// C++ program to print and
// remove leaf nodes
 
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};
 
map<int, vector<int> > resultMap;
 
// Function to store depth of each nodes
int fillMap(Node* root)
{
    if (root == nullptr)
        return 0;
    int LsubTreeDepth = fillMap(root->left);
    int RsubTreeDepth = fillMap(root->right);
    int depth = max(LsubTreeDepth,
                    RsubTreeDepth)
                + 1;
    resultMap[depth].push_back(root->data);
    return depth;
}
 
// Print and remove leaf nodes
void printLeafNodes(Node* root)
{
 
    // If node is null, return
    if (!root)
        return;
 
    // maxDepth from tree
    int maxDepth = fillMap(root);
    for (int i = 1; i <= maxDepth; i++) {
        vector<int> tempVector
            = resultMap[i];
        int vSize = tempVector.size();
 
        // Print leaf nodes
        // from each iteration
        cout << "Iteration " << i << " : ";
        for (int j = 0; j < vSize; j++)
            cout << tempVector[j] << " ";
        cout << "\n";
    }
}
 
// Utility function to
// create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Driver Code
int main()
{
    // Create binary tree
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    // Print leaf nodes of the given tree
    printLeafNodes(root);
    return 0;
}

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
    // A Binary Tree Node
    public class Node {
        public int data;
        public Node left, right;
    };
 
    static Dictionary<int, List<int>> resultMap = new Dictionary<int, List<int>>();
 
    // Function to store depth of each nodes
    static int fillMap(Node root)
    {
        if (root == null)
            return 0;
 
        int LsubTreeDepth = fillMap(root.left);
        int RsubTreeDepth = fillMap(root.right);
        int depth = Math.Max(LsubTreeDepth,  RsubTreeDepth) + 1;
 
        if(!resultMap.ContainsKey(depth)){
            resultMap.Add(depth, new List<int>());
        }
        resultMap[depth].Add(root.data);
        return depth;
    }
 
    // Print and remove leaf nodes
    static void printLeafNodes(Node root)
    {
 
        // If node is null, return
        if (root == null)
            return;
 
        // maxDepth from tree
        int maxDepth = fillMap(root);
        for (int i = 1; i <= maxDepth; i++) {
            List<int> tempVector = resultMap[i];
            int vSize = tempVector.Count;
 
            // Print leaf nodes
            // from each iteration
            Console.Write("Iteration " + i + " : ");
            for (int j = 0 ; j < vSize ; j++)
                Console.Write(tempVector[j] + " ");
            Console.WriteLine("");
        }
    }
 
    // Utility function to
    // create a new tree node
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.left = temp.right = null;
        return temp;
    }
 
    public static void Main(string[] args){
         
        // Create binary tree
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
        root.left.left = newNode(4);
        root.left.right = newNode(5);
 
        // Print leaf nodes of the given tree
        printLeafNodes(root);
 
    }
}
 
// This code is contributed by entertain2022.

Iteration 1 : 4 5 3 
Iteration 2 : 2 
Iteration 3 : 1 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)