Considere un árbol binario enraizado representado mediante punteros. El mejor límite superior del tiempo requerido para determinar el número de subárboles que tienen exactamente 4 Nodes O(n a Logn b ). Entonces el valor de a + 10b es ________
(A) 1
(B) 11
(C) 12
(D) 21
Respuesta: (A)
Explicación: Podemos encontrar el subárbol con 4 Nodes en tiempo O(n). El siguiente puede ser un enfoque simple.
1) Atraviese el árbol de abajo hacia arriba y encuentre el tamaño del subárbol enraizado con el Node actual
2) Si el tamaño se convierte en 4, imprima el Node actual.
La siguiente es la implementación de C
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new Binary Tree Node
struct Node *newNode(int item)
{
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int print4Subtree(struct Node *root)
{
if (root == NULL)
return 0;
int l = print4Subtree(root->left);
int r = print4Subtree(root->right);
if ((l + r + 1) == 4)
printf("%d ", root->data);
return (l + r + 1);
}
// Driver Program to test above functions
int main()
{
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
print4Subtree(root);
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA