Comment trouver le premier ancêtre commun d'un nœud dans un arbre binaire?
-
12-11-2019 - |
Question
Voici mon algorithme pour trouver le premier ancêtre commun. Mais je ne sais pas comment calculer sa complexité du temps, quelqu'un peut-il aider?
public Tree commonAncestor(Tree root, Tree p, Tree q) {
if (covers(root.left, p) && covers(root.left, q))
return commonAncestor(root.left, p, q);
if (covers(root.right, p) && covers(root.right, q))
return commonAncestor(root.right, p, q);
return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow