Diferència Màxima. X71480

Les fulles d’un arbre binari són els nodes que no tenen ni fill dret ni fill esquerre. Un camí és una seqüència de nodes d’un arbre A $[a_1, a_2, \dots, a_i, a_{i+1}, \dots, a_n]$ tal que $a_1$ és l’arrel d’$A$, $a_n$ és una fulla, i per a tot $a_i$ ($i < n$) tenim que $a_{i+1}$ és el fill de $a_i$. Un arbre A té tants camins com fulles. La mida d’un camí és el nombre de nodes de què es composa.

Feu la funció recursiva

int diferenciaMaxima (const arbreBin<int>);

tal que, donat un arbre binari A, torni la diferència entre la mida del camí més llarg i el més curt d’A.

Per exemple, per a l’arbre A1, tenim els camins $[1,2,5],[1,2,6],[1,3,7],[1,3,8]$, i tots tenen mida $3$. Per tant, diferenciaMaxima(A1) tornarà $0$.

L’arbre A2 té els camins $[1,2],[1,3,7]$ de mides $2$ i $3$, i per tant, diferenciaMaxima(A2) tornarà $1$.

L’arbre A3 té els camins $[1,2],[1,3,7],[1,3,2]$ de mides $2$, $3$ i $3$, i per tant, diferenciaMaxima(A3) tornarà $1$.

         A1            A2         A3

         1             1           1
        / \           / \         / \
       2   3         2   3       2   3
      / \ / \           /           / \
     5  6 7  8         7           7   2
                    

Entrada

La funció rep un arbre binari d’enters A.

Sortida

La diferència entre la mida del camí més llarg i el més curt d’A.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar diferenciaMaxima.cpp

Observeu que per compilar us donem el Makefile,

la capçalera del mòdul funcional diferenciaMaxima.hpp,

la implementació de l’arbre binari arbreBin.hpp i el programa principal program.cpp.

Jutge.org també us donarà un semàfor verd si envieu una solució iterativa, però no serà correcte ja que l’enunciat del problema demana que la solució enviada sigui recursiva.