Je veux compter le non des nœuds de feuilles:
Remarque: Impossible d'utiliser une variable de niveau global / de classe
I IMPORTEMED après l'algo, et ça marche bien. Mais je veux que la méthode signature soit Je sais que je peux surcharger des méthds et appeler la méthode 2 args SIG de 1 ARG, mais ne voulez pas Est-ce que quelqu'un suggère une autre méthode? P> int countLeaves(Node node,int count){
if(node==null)
return 0;
if(node.left==null && node.right==null){
return 1+count;
}else{
int lc = countLeaves(node.left, count);
int total = countLeaves(node.right, lc);
return total;
}
}
7 Réponses :
remplir ??? code> set vous-même. int countLeaves(Node node){
if (node==null)
return 0;
if (node.left==null && node.right==null){
return 1;
} else {
int lc = countLeaves(node.left);
int rc = countLeaves(node.right);
return ???;
}
}
int countLeaves(Node node){
if( node == null )
return 0;
if( node.left == null && node.right == null ) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}
You are doing the same thing as before but instead of holding the current count as we go, we simply say return the result of the sum of the left and right node. These in turn recurse down till they hit the basecases.
Vous n'avez pas besoin de passer compter vers le bas de la pile d'appels, uniquement à partir de:
public int getLeafsCount(BSTNode<T> node, int count) {
if(node == null || node.getData() == null){
return count;
}
else if(isLeaf(node)){
return ++count;
}else{
int leafsLeft = getLeafsCount((BSTNode<T>) node.getLeft(), count);
int leafsCount = getLeafsCount((BSTNode<T>) node.getRight(), leafsLeft);
return leafsCount;
}
}
Vous devriez éditer votre message précédent au lieu d'en ajouter un nouveau.
Nous pouvons appliquer deux approches, l'une est récursive et une autre est itérative (implémentation basée sur la file d'attente). Mais je vais expliquer les deux méthodes.
solution récursive forte> p> int count_leaf(Node root)
{
int count=0;
if(root==NULL)
return 0;
queue<Node *> myqueue;
myqueue.push(root);
while(!myqueue.empty())
{
Node temp;
temp=myqueue.top(); //Take the front element of queue
myqueue.pop(); //remove the front element of queue
if(temp->left==NULL && temp->right==NULL)
count++;
if(temp->left)
myqueue.push(temp->left);
if(temp->right)
myqueue.push(temp->right);
}
return count;
}
Merci pour la solution - je l'ai incorporé ici -
Une méthode itérative est bonne pour ma mise en œuvre car je souhaite, à partir de tout nœud donné, combien de gauche S vs. code> droit s. Donc, quand j'ai un déséquilibre, je peux faire pivoter les nœuds.
Comme je suis toujours unitaire teste cette mise en œuvre, aucune promesse d'exploitation sans bug n'est faite. S'il existe des problèmes particuliers avec la mise en œuvre, je suis heureux de recevoir les commentaires. Strong> Initialement, je reçois des résultats favorables: P> var actLeftCount = CountNode(root, Direction.Left);
var actRightCount = CountNode(root, Direction.Right);
même que dans le premier commentaire.