Dado un árbol binario , la tarea es eliminar los Nodes hoja del árbol binario durante cada operación e imprimir el recuento.
Ejemplos:
Aporte:
Salida: 4 2 1 1
Explicación:
En la primera operación, eliminando los Nodes hoja { 1, 3, 4, 6 } del árbol binario.
En la segunda operación eliminando los Nodes hoja { 8, 7 }
En la tercera operación eliminando los Nodes hoja { 5 }
En la cuarta operación eliminando los Nodes hoja { 2 }
Por lo tanto, el recuento de Nodes hoja eliminados en cada operación 4 2 1 1 .Aporte:
Salida: 2 1
Enfoque ingenuo: el enfoque más simple para resolver este problema consiste en atravesar repetidamente el árbol para cada operación e imprimir el recuento de Nodes hoja actualmente presentes en el árbol binario y eliminar todos los Nodes hoja del árbol binario .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que un Node no se elimina a menos que sus dos elementos secundarios ya se hayan eliminado. Por lo tanto, se puede determinar en qué paso se eliminará un Node, que será igual a 1 + la longitud máxima de la ruta desde ese Node hasta cualquier Node hoja en el subárbol con raíz en ese Node . Siga los pasos a continuación para resolver este problema:
- Inicialice un Map , digamos M , para almacenar los Nodes hoja en cada eliminación del árbol.
- Realice un recorrido DFS en el árbol binario dado siguiendo los pasos a continuación:
- Compruebe si el Node dado es NULL o no. Si se encuentra que es cierto, devuelve 0 .
- De lo contrario, llame recursivamente a los Nodes izquierdo y derecho y almacene los valores devueltos.
- Encuentre la altura máxima, digamos maxHeight , cuando cada Node sea un Node hoja como (1 + máximo de los valores devueltos por las llamadas recursivas izquierda y derecha) en los pasos anteriores para cada Node.
- Inserte el Node actual en el Mapa M en la clave maxHeight .
- Después de completar los pasos anteriores, imprima el recuento de Nodes hoja almacenados en el Mapa después de cada eliminación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a
// Binary Tree Node
struct Node {
int data;
Node *left, *right;
};
// Function to allocate
// a new tree node
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// Function to find the maximum height
// from leaf in the subtree rooted at
// current node and add that to hashmap
int maxHeightToLeafUTIL(
Node* curr, map<int, vector<int> >& mp)
{
if (curr == NULL) {
return 0;
}
// Max height to leaf in left subtree
int leftLeaf
= maxHeightToLeafUTIL(curr->left, mp);
// Max height to leaf in right subtree
int rightLeaf
= maxHeightToLeafUTIL(curr->right, mp);
// Max height to leaf in current subtree
int maxHeightSubtree
= 1 + max(leftLeaf, rightLeaf);
// Adding current node to the Map
mp[maxHeightSubtree].push_back(
curr->data);
return maxHeightSubtree;
}
// Function to find the count of leaf nodes
// by repeatedly removing the leaf nodes
void printAndDelete(Node* root)
{
// Stores the leaf deletion with
// each iteration
map<int, vector<int> > mp;
// Function Call to find the order
// of deletion of nodes
maxHeightToLeafUTIL(root, mp);
// Printing the map values
for (auto step : mp) {
cout << mp[step.first].size() << " ";
}
}
// Driver code
int main()
{
// Given Binary Tree
Node* root = newNode(2);
root->right = newNode(7);
root->right->right = newNode(6);
root->left = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(8);
root->left->right->left = newNode(3);
root->left->right->right = newNode(4);
/*
Input :
2
/ \
5 7
/ \ \
1 8 6
/ \
3 4
*/
// Function Call
printAndDelete(root);
return 0;
}
// This code is contributed by pragup
Java
// Java program for the above approach
import java.util.*;
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class GFG
{
Node root;
// Function to find the maximum height
// from leaf in the subtree rooted at
// current node and add that to hashmap
static int maxHeightToLeafUTIL(
Node curr, Map<Integer, ArrayList<Integer> > mp)
{
if (curr == null)
{
return 0;
}
// Max height to leaf in left subtree
int leftLeaf
= maxHeightToLeafUTIL(curr.left, mp);
// Max height to leaf in right subtree
int rightLeaf
= maxHeightToLeafUTIL(curr.right, mp);
// Max height to leaf in current subtree
int maxHeightSubtree
= 1 + Math.max(leftLeaf, rightLeaf);
// Adding current node to the Map
if(!mp.containsKey(maxHeightSubtree))
{
mp.put(maxHeightSubtree, new ArrayList<>());
}
mp.get(maxHeightSubtree).add(curr.data);
return maxHeightSubtree;
}
// Function to find the count of leaf nodes
// by repeatedly removing the leaf nodes
static void printAndDelete(Node root)
{
// Stores the leaf deletion with
// each iteration
Map<Integer, ArrayList<Integer> > mp=new HashMap<>();
// Function Call to find the order
// of deletion of nodes
maxHeightToLeafUTIL(root, mp);
// Printing the map values
for (Map.Entry<Integer,ArrayList<Integer>> k:mp.entrySet())
{
System.out.print(k.getValue().size() + " ");
}
}
// Driver code
public static void main (String[] args)
{
GFG tree = new GFG();
tree.root = new Node(2);
tree.root.left = new Node(5);
tree.root.right = new Node(7);
tree.root.right.right = new Node(6);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(8);
tree.root.left.right.left = new Node(3);
tree.root.left.right.right = new Node(4);
/*
Input :
2
/ \
5 7
/ \ \
1 8 6
/ \
3 4
*/
// Function Call
printAndDelete(tree.root);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Tree node structure used in the program class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Function to find the maximum height # from leaf in the subtree rooted at # current node and add that to hashmap def maxHeightToLeafUTIL(curr): global mp if (curr == None): return 0 # Max height to leaf in left subtree leftLeaf = maxHeightToLeafUTIL(curr.left) # Max height to leaf in right subtree rightLeaf = maxHeightToLeafUTIL(curr.right) # Max height to leaf in current subtree maxHeightSubtree = 1 + max(leftLeaf, rightLeaf) # Adding current node to the Map mp[maxHeightSubtree].append(curr.data) return maxHeightSubtree # Function to find the count of leaf nodes # by repeatedly removing the leaf nodes def printAndDelete(root): global mp # Function Call to find the order # of deletion of nodes maxHeightToLeafUTIL(root) for step in mp: if len(step): print(len(step), end = " ") # Driver code if __name__ == '__main__': mp = [[] for i in range(1000)] # Given Binary Tree root = Node(2) root.right = Node(7) root.right.right = Node(6) root.left = Node(5) root.left.left = Node(1) root.left.right = Node(8) root.left.right.left = Node(3) root.left.right.right = Node(4) # # # Input : # 2 # / \ # 5 7 # / \ \ # 1 8 6 # / \ # 3 4 # Function Call printAndDelete(root) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class GFG{
Node root;
// Function to find the maximum height
// from leaf in the subtree rooted at
// current node and add that to hashmap
static int maxHeightToLeafUTIL(
Node curr, Dictionary<int, List<int> > mp)
{
if (curr == null)
{
return 0;
}
// Max height to leaf in left subtree
int leftLeaf
= maxHeightToLeafUTIL(curr.left, mp);
// Max height to leaf in right subtree
int rightLeaf
= maxHeightToLeafUTIL(curr.right, mp);
// Max height to leaf in current subtree
int maxHeightSubtree
= 1 + Math.Max(leftLeaf, rightLeaf);
// Adding current node to the Map
if(!mp.ContainsKey(maxHeightSubtree))
{
mp.Add(maxHeightSubtree, new List<int>());
}
mp[maxHeightSubtree].Add(curr.data);
return maxHeightSubtree;
}
// Function to find the count of leaf nodes
// by repeatedly removing the leaf nodes
static void printAndDelete(Node root)
{
// Stores the leaf deletion with
// each iteration
Dictionary<int, List<int> > mp=new Dictionary<int, List<int> >();
// Function Call to find the order
// of deletion of nodes
maxHeightToLeafUTIL(root, mp);
// Printing the map values
foreach(KeyValuePair<int, List<int>> k in mp)
{
Console.Write(k.Value.Count + " ");
}
}
// Driver code
static public void Main (){
GFG tree = new GFG();
tree.root = new Node(2);
tree.root.left = new Node(5);
tree.root.right = new Node(7);
tree.root.right.right = new Node(6);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(8);
tree.root.left.right.left = new Node(3);
tree.root.left.right.right = new Node(4);
/*
Input :
2
/ \
5 7
/ \ \
1 8 6
/ \
3 4
*/
// Function Call
printAndDelete(tree.root);
}
}
Javascript
<script>
// JavaScript program to implement the above approach
// Structure of a tree node
class Node
{
constructor(item) {
this.left = null;
this.right = null;
this.data = item;
}
}
let root;
class GFG
{
constructor() {
}
}
// Function to find the maximum height
// from leaf in the subtree rooted at
// current node and add that to hashmap
function maxHeightToLeafUTIL(curr, mp)
{
if (curr == null)
{
return 0;
}
// Max height to leaf in left subtree
let leftLeaf
= maxHeightToLeafUTIL(curr.left, mp);
// Max height to leaf in right subtree
let rightLeaf
= maxHeightToLeafUTIL(curr.right, mp);
// Max height to leaf in current subtree
let maxHeightSubtree
= 1 + Math.max(leftLeaf, rightLeaf);
// Adding current node to the Map
if(!mp.has(maxHeightSubtree))
{
mp.set(maxHeightSubtree, []);
}
mp.get(maxHeightSubtree).push(curr.data);
return maxHeightSubtree;
}
// Function to find the count of leaf nodes
// by repeatedly removing the leaf nodes
function printAndDelete(root)
{
// Stores the leaf deletion with
// each iteration
let mp = new Map();
// Function Call to find the order
// of deletion of nodes
maxHeightToLeafUTIL(root, mp);
// Printing the map values
mp.forEach((values,keys)=>{
document.write(values.length + " ")
})
}
let tree = new GFG();
tree.root = new Node(2);
tree.root.left = new Node(5);
tree.root.right = new Node(7);
tree.root.right.right = new Node(6);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(8);
tree.root.left.right.left = new Node(3);
tree.root.left.right.right = new Node(4);
/*
Input :
2
/ \
5 7
/ \ \
1 8 6
/ \
3 4
*/
// Function Call
printAndDelete(tree.root);
</script>
Producción:
4 2 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)