Dada una raíz de árbol N-ario , la tarea es encontrar el recuento de Nodes de modo que su subárbol sea un árbol binario.
Ejemplo:
Entrada: Árbol en la imagen de abajo
Salida: 11
Explicación: Los Nodes en los que el subárbol es un árbol binario son {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}.Entrada: Árbol en la imagen de abajo
Salida: 9
Enfoque: El problema dado se puede resolver utilizando el recorrido posterior al pedido . La idea es usar la recursividad y verificar si el Node actual contiene como máximo 2 hijos y si los hijos son árboles binarios válidos. Se pueden seguir los siguientes pasos para resolver el problema:
- Aplique el recorrido posterior al pedido en el árbol N-ario :
- Agregue los valores devueltos de cada Node secundario para calcular la cantidad de árboles binarios encontrados en ese Node y guárdelo en suma
- Si la raíz tiene como máximo dos hijos que son árboles binarios válidos, entonces la raíz también es un árbol binario, por lo que devuelve un par de suma + 1 y 1 para indicar un árbol binario válido
- Si la raíz tiene más de dos Nodes secundarios o alguno de los elementos secundarios no son árboles binarios válidos, devuelva el par de suma y 0 para indicar un árbol binario no válido.
- Devuelve el valor en la primera suma de índice, del par devuelto del recorrido posterior al pedido .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
vector<Node *> children;
int val;
// constructor
Node(int v)
{
val = v;
children = {};
}
};
// Post-order traversal to find
// depth of all branches of every
// node of the tree
vector<int> postOrder(Node *root)
{
// Initialize a variable sum to
// count number of binary trees
int sum = 0;
// Integer to indicate if the tree
// rooted at current root is a
// valid binary tree
int valid = 1;
// Use recursion on all child nodes
for (Node *child : root->children)
{
// Get the number of binary trees
vector<int> binTrees = postOrder(child);
// If tree rooted at current child
// is not a valid binary tree then
// tree rooted at current root is
// also not a valid binary tree
if (binTrees[1] == 0)
valid = 0;
// If branches are unbalanced
// then store -1 in height
sum += binTrees[0];
}
// Children are valid binary trees
// and the number of children
// are less than 3
if (valid == 1 && root->children.size() < 3)
{
// Root is also a valid binary tree
sum++;
}
// Children are leaf nodes but number
// of children are greater than 2
else
valid = 0;
// Return the answer
return {sum, valid};
}
// Function to find the number of
// binary trees in an N-ary tree
int binTreesGeneric(Node *root)
{
// Base case
if (root == NULL)
return 0;
// Apply post-order traversal on
// the root and return the answer
return postOrder(root)[0];
}
// Driver code
int main()
{
// Initialize the graph
Node *twenty = new Node(20);
Node *seven = new Node(7);
Node *seven2 = new Node(7);
Node *five = new Node(5);
Node *four = new Node(4);
Node *nine = new Node(9);
Node *one = new Node(1);
Node *two = new Node(2);
Node *six = new Node(6);
Node *eight = new Node(8);
Node *ten = new Node(10);
Node *three = new Node(3);
Node *mfour = new Node(11);
Node *zero = new Node(12);
three->children.push_back(mfour);
three->children.push_back(zero);
ten->children.push_back(three);
two->children.push_back(six);
two->children.push_back(seven2);
four->children.push_back(nine);
four->children.push_back(one);
four->children.push_back(five);
seven->children.push_back(ten);
seven->children.push_back(two);
seven->children.push_back(eight);
seven->children.push_back(four);
twenty->children.push_back(seven);
// Call the function
// and print the result
cout << (binTreesGeneric(twenty));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
static class Node {
List<Node> children;
int val;
// constructor
public Node(int val)
{
this.val = val;
children = new ArrayList<>();
}
}
// Function to find the number of
// binary trees in an N-ary tree
public static int binTreesGeneric(Node root)
{
// Base case
if (root == null)
return 0;
// Apply post-order traversal on
// the root and return the answer
return postOrder(root)[0];
}
// Post-order traversal to find
// depth of all branches of every
// node of the tree
public static int[] postOrder(Node root)
{
// Initialize a variable sum to
// count number of binary trees
int sum = 0;
// Integer to indicate if the tree
// rooted at current root is a
// valid binary tree
int valid = 1;
// Use recursion on all child nodes
for (Node child : root.children) {
// Get the number of binary trees
int[] binTrees = postOrder(child);
// If tree rooted at current child
// is not a valid binary tree then
// tree rooted at current root is
// also not a valid binary tree
if (binTrees[1] == 0)
valid = 0;
// If branches are unbalanced
// then store -1 in height
sum += binTrees[0];
}
// Children are valid binary trees
// and the number of children
// are less than 3
if (valid == 1 && root.children.size() < 3) {
// Root is also a valid binary tree
sum++;
}
// Children are leaf nodes but number
// of children are greater than 2
else
valid = 0;
// Return the answer
return new int[] { sum, valid };
}
// Driver code
public static void main(String[] args)
{
// Initialize the graph
Node twenty = new Node(20);
Node seven = new Node(7);
Node seven2 = new Node(7);
Node five = new Node(5);
Node four = new Node(4);
Node nine = new Node(9);
Node one = new Node(1);
Node two = new Node(2);
Node six = new Node(6);
Node eight = new Node(8);
Node ten = new Node(10);
Node three = new Node(3);
Node mfour = new Node(11);
Node zero = new Node(12);
three.children.add(mfour);
three.children.add(zero);
ten.children.add(three);
two.children.add(six);
two.children.add(seven2);
four.children.add(nine);
four.children.add(one);
four.children.add(five);
seven.children.add(ten);
seven.children.add(two);
seven.children.add(eight);
seven.children.add(four);
twenty.children.add(seven);
// Call the function
// and print the result
System.out.println(
binTreesGeneric(twenty));
}
}
Python3
# Python code for the above approach class Node: # constructor def __init__(self, v): self.val = v; self.children = []; # Post-order traversal to find # depth of all branches of every # node of the tree def postOrder(root): # Initialize a variable sum to # count number of binary trees sum = 0; # Integer to indicate if the tree # rooted at current root is a # valid binary tree valid = 1; # Use recursion on all child nodes for child in root.children: # Get the number of binary trees binTrees = postOrder(child); # If tree rooted at current child # is not a valid binary tree then # tree rooted at current root is # also not a valid binary tree if (binTrees[1] == 0): valid = 0; # If branches are unbalanced # then store -1 in height sum += binTrees[0]; # Children are valid binary trees # and the number of children # are less than 3 if (valid == 1 and len(root.children) < 3): # Root is also a valid binary tree sum += 1 # Children are leaf nodes but number # of children are greater than 2 else: valid = 0; # Return the answer return [ sum, valid ]; # Function to find the number of # binary trees in an N-ary tree def binTreesGeneric(root): # Base case if (root == None): return 0; # Apply post-order traversal on # the root and return the answer return postOrder(root)[0]; # Driver code # Initialize the graph twenty = Node(20); seven = Node(7); seven2 = Node(7); five = Node(5); four = Node(4); nine = Node(9); one = Node(1); two = Node(2); six = Node(6); eight = Node(8); ten = Node(10); three = Node(3); mfour = Node(11); zero = Node(12); three.children.append(mfour); three.children.append(zero); ten.children.append(three); two.children.append(six); two.children.append(seven2); four.children.append(nine); four.children.append(one); four.children.append(five); seven.children.append(ten); seven.children.append(two); seven.children.append(eight); seven.children.append(four); twenty.children.append(seven); # Call the function # and print the result print((binTreesGeneric(twenty))); # This code is contributed by gfgking
Javascript
<script>
// Javascript code for the above approach
class Node {
// constructor
constructor(v) {
this.val = v;
this.children = [];
}
};
// Post-order traversal to find
// depth of all branches of every
// node of the tree
function postOrder(root) {
// Initialize a variable sum to
// count number of binary trees
let sum = 0;
// Integer to indicate if the tree
// rooted at current root is a
// valid binary tree
let valid = 1;
// Use recursion on all child nodes
for (child of root.children) {
// Get the number of binary trees
let binTrees = postOrder(child);
// If tree rooted at current child
// is not a valid binary tree then
// tree rooted at current root is
// also not a valid binary tree
if (binTrees[1] == 0)
valid = 0;
// If branches are unbalanced
// then store -1 in height
sum += binTrees[0];
}
// Children are valid binary trees
// and the number of children
// are less than 3
if (valid == 1 && root.children.length < 3) {
// Root is also a valid binary tree
sum++;
}
// Children are leaf nodes but number
// of children are greater than 2
else
valid = 0;
// Return the answer
return [ sum, valid ];
}
// Function to find the number of
// binary trees in an N-ary tree
function binTreesGeneric(root) {
// Base case
if (root == null)
return 0;
// Apply post-order traversal on
// the root and return the answer
return postOrder(root)[0];
}
// Driver code
// Initialize the graph
let twenty = new Node(20);
let seven = new Node(7);
let seven2 = new Node(7);
let five = new Node(5);
let four = new Node(4);
let nine = new Node(9);
let one = new Node(1);
let two = new Node(2);
let six = new Node(6);
let eight = new Node(8);
let ten = new Node(10);
let three = new Node(3);
let mfour = new Node(11);
let zero = new Node(12);
three.children.push(mfour);
three.children.push(zero);
ten.children.push(three);
two.children.push(six);
two.children.push(seven2);
four.children.push(nine);
four.children.push(one);
four.children.push(five);
seven.children.push(ten);
seven.children.push(two);
seven.children.push(eight);
seven.children.push(four);
twenty.children.push(seven);
// Call the function
// and print the result
document.write((binTreesGeneric(twenty)));
// This code is contributed by gfgking
</script>
Producción
11
Complejidad temporal: O(N)
Espacio auxiliar: O(N)