Dado un árbol binario donde los valores de los Nodes son alfabetos en minúsculas, la tarea es encontrar el diámetro lexicográficamente más pequeño. El diámetro es el camino más largo entre dos Nodes hoja, por lo tanto, puede haber múltiples diámetros en un árbol binario. La tarea es imprimir el diámetro lexicográficamente más pequeño entre todos los diámetros posibles.
Ejemplos:
Input:
a
/ \
b c
/ \ / \
d e f g
Output: Diameter: 5
Lexicographically smallest diameter: d b a c f
Explanation:
Note that there are many other paths
exist like {d, b, a, c, g},
{e, b, a, c, f} and {e, b, a, c, g}
but {d, b, a, c, f}
is lexicographically smallest
Input:
k
/ \
e s
/ \
g f
Output: Diameter: 4
Lexicographically smallest diameter: f e k s
Explanation:
Note that many other paths
exist like {g, e, k, s}
{s, k, e, g} and {s, k, e, f}
but {f, e, k, s} is
lexicographically smallest
Enfoque:
El enfoque es similar a encontrar el diámetro como se discutió en la publicación anterior . Ahora viene la parte de
imprimir el camino más largo con el diámetro máximo y lexicográficamente más pequeño.
Pasos:
- La función de comparación personalizada devuelve el vector lexicográfico más pequeño.
- Se han mantenido seis tipos de vectores que contienen
el subárbol izquierdo (de un Node) Nodes en el diámetro
izquierdo el subárbol derecho (de un Node) Nodes en el diámetro derecho
Nodes que ocurren en la altura izquierda (de un Node)
Nodes que ocurren en la altura derecha (de un Node) a node)
heightv vector contiene los Nodes que ocurren en la ruta de altura máxima
dia vector contiene los Nodes que ocurren en la ruta de altura máxima
- El resto se explica en los comentarios del código y será difícil explicarlo aquí con palabras.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct node {
char data;
node *left, *right;
};
// Utility function to create a new node
node* newNode(char data)
{
node* c = new node;
c->data = data;
c->left = c->right = NULL;
return c;
}
// Function to compare and return
// lexicographically smallest vector
vector<node*> compare(vector<node*> a, vector<node*> b)
{
for (int i = 0; i < a.size() && i < b.size(); i++) {
if (a[i]->data < b[i]->data) {
return a;
}
if (a[i]->data > b[i]->data) {
return b;
}
}
return a;
}
// Function to find diameter
int diameter(node* root, int& height, vector<node*>& dia,
vector<node*>& heightv)
{
// If root is null
if (!root) {
height = 0;
return 0;
}
// Left height and right height
// respectively
int lh = 0, rh = 0;
// Left tree diameter and
// right tree diameter
int ld, rd;
vector<node*> leftdia;
vector<node*> rightdia;
vector<node*> leftheight;
vector<node*> rightheight;
// Left subtree diameter
ld = diameter(root->left, lh, leftdia, leftheight);
// Right subtree diameter
rd = diameter(root->right, rh, rightdia, rightheight);
// If left height is more
// than right tree height
if (lh > rh) {
// Add current root so lh + 1
height = lh + 1;
// Change vector heightv to leftheight
heightv = leftheight;
// Insert current root in the path
heightv.push_back(root);
}
// If right height is
// more than left tree height
else if (rh > lh) {
// Add current root so rh + 1
height = rh + 1;
// Change vector heightv to rightheight
heightv = rightheight;
// Insert current root in the path
heightv.push_back(root);
}
// Both height same compare
// lexicographically now
else {
// Add current root so rh + 1
height = rh + 1;
// Lexicographical comparison between two vectors
heightv = compare(leftheight, rightheight);
// Insert current root in the path
heightv.push_back(root);
}
// If distance of one leaf node to another leaf
// containing the root is more than the left
// diameter and right diameter
if (lh + rh + 1 > max(ld, rd)) {
// Make dia equal to leftheight
dia = leftheight;
// Add current root into it
dia.push_back(root);
for (int j = rightheight.size() - 1; j >= 0; j--) {
// Add right tree (right to root) nodes
dia.push_back(rightheight[j]);
}
}
// If either leftdiameter containing the left
// subtree and root or rightdiameter containing
// the right subtree and root is more than
// above lh+rh+1
else {
// If diameter of left tree is
// greater our answer vector i.e
// dia is equal to leftdia then
if (ld > rd) {
dia = leftdia;
}
// If both diameter
// same check lexicographically
else if (ld == rd) {
dia = compare(leftdia, rightdia);
}
// If diameter of right tree
// is greater our answer vector
// i.e dia is equal to rightdia then
else {
dia = rightdia;
}
}
return dia.size();
}
// Driver code
int main()
{
node* root = newNode('a');
root->left = newNode('b');
root->right = newNode('c');
root->left->left = newNode('d');
root->left->right = newNode('e');
root->right->left = newNode('f');
root->right->right = newNode('g');
int height = 0;
vector<node *> dia, heigh;
cout << "Diameter is: " << diameter(root, height,
dia, heigh)
<< endl;
// Printing the lexicographically smallest diameter
cout << "Lexicographically smallest diameter:" << endl;
for (int j = 0; j < dia.size(); j++) {
cout << dia[j]->data << " ";
}
return 0;
}
Producción:
Diameter is: 5 Lexicographically smallest diameter: d b a c f