Hola.
No entiendo muy bien la pregunta.
Si lo que propones es usar la función caminoMasLargo para armar una lista y luego contar sus largo, no, esa no es la idea.
Te sugiero que pienses un algoritmo que a medida que recorre el árbol y visita cada nodo vaya "contando" (o descontando) los nodos visitados.
Saludos