Comment puis-je trouver la profondeur et la hauteur de tous les nœuds dans un semi-cheminée délimitée?

Question

J'écris un programme où j'ai un semi-cheminée délimitée (il a un élément racine en haut, tous les bords pointent vers le bas et un nœud peut avoir plusieurs parents). J'ai besoin de précomputer la profondeur de chaque nœud (le nombre maximum de bords du nœud racine) et de la hauteur (le nombre maximum de bords à n'importe quelle feuille). J'ai une implémentation naïve pour les hauteurs où chaque nœud est comparé à tous ses descendants, donc probablement O (n ^ 2). Qu'est-ce qu'un algorithme plus rapide qui calcule à la fois la hauteur et la profondeur?