Come trovare il primo antenato comune di un nodo in un albero binario?
-
12-11-2019 - |
Domanda
Di seguito è il mio algoritmo per trovare il primo antenato comune. Ma non so come calcolare la complessità del tempo, qualcuno può aiutare?
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);
}
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow