J'essaie cette Problème sur la pratique -Il, mais j'ai eu des problèmes avec beaucoup de temps.
Écrivez une méthode correspondante qui renvoie un nombre de nœuds dans un arbre qui correspond à des nœuds dans un autre arbre. Une correspondance est définie comme une paire de nœuds situés dans la même position dans les deux arbres par rapport à leur racine globale et qui stockent les mêmes données. P> BlockQuote>
Jusqu'à présent, j'ai essayé ce qui suit ci-dessous, mais je ne comprends pas vraiment le comte que je veux, et je ne suis pas tout à fait sûr pourquoi. P>
P>
public int matches(IntTree t2) { return match(overallRoot, t2.overallRoot); } public int match(IntTreeNode tree1, IntTreeNode tree2) { if(tree1 == null && tree2 == null) return 1; if(tree1 == null || tree2 == null) return 0; if(tree1.data == tree2.data) return 1; int left = match(tree1.left, tree2.left); int right = match(tree1.right, tree2.right); return left + right; }
3 Réponses :
Vous arrêtez votre recherche si le nœud actuel correspond. Si c'est différent, vous vérifiez à gauche et à droite, mais sur un match, vous le renvoyez.
Vous êtes très proche de la solution, vous devez envisager:
pour les deux racines sont différentes, le nombre est 0 sinon est 1 et après que vous puissiez calculer le nombre compter pour les deux sous-arraches ajoutant au nombre pour les deux racines.
ci-dessous mes suggestions sous forme de code: xxx
Réponse complète pour la pratique en la pratique:
int matches(IntTree tree2) {
return matches(tree2.overallRoot, this.overallRoot);
}
int matches(IntTreeNode tree1, IntTreeNode node2)
{
int left=0, right=0, count =0;
if(tree1 == null && this != null || this == null && tree1 != null) { return 0; }
count = tree1.data == node2.data ? 1 : 0;
if(tree1.left != null && node2.left !=null){
left = matches(tree1.left, node2.left);}
if(tree1.right != null && node2.right !=null){
right = matches(tree1.right, node2.right);}
return count + left + right;
}
Pourquoi considérons-tu des arbres vides (
null ) étant égal en tant que match? En outre, pourquoi revenez-vous lorsque deux nœuds d'arbres ont les mêmes données, même si leurs sous-arbres pourraient avoir encore plus de matchs?