comment trouver la hauteur d'un nœud d'un arbre binaire de manière récursive
path = 0 # the lenght of the path
while self.right != None or self.left != None:
while self.right != None:
self = self.right
path = path +1
while self.left != None:
self = self.left
path = path +1
return path
c'est mon exemple de code pour trouver la Hauteur est définie comme la longueur de la
plus long chemin par le nombre de nœuds de l'auto à une feuille. La hauteur d'un nœud feuille est 1.
il ne fonctionne pas.
Vous avez une question?
La question, même si implicite, est assez évident, vous ne pensez pas?
cette question implicite étant "gimme teh codez", à droite?
En fait, j'ai juste besoin d'un algorithme. Parce que, mon code ne fonctionne pas. Et si vous connaissez la solution, peut-être le pseudo-code 😛
Ma conjecture est la suivante: "pourquoi n'est-ce pas?" L'affiche semble avoir du mal avec l'anglais, donc, je voudrais lui donner une pause ici. Cela étant dit, je ne voudrais pas donner le code (car il ressemble à un devoirs à la maison pour moi), mais d'en expliquer quelques-uns des plus flagrantes erreurs qu'il a fait.
La question, même si implicite, est assez évident, vous ne pensez pas?
cette question implicite étant "gimme teh codez", à droite?
En fait, j'ai juste besoin d'un algorithme. Parce que, mon code ne fonctionne pas. Et si vous connaissez la solution, peut-être le pseudo-code 😛
Ma conjecture est la suivante: "pourquoi n'est-ce pas?" L'affiche semble avoir du mal avec l'anglais, donc, je voudrais lui donner une pause ici. Cela étant dit, je ne voudrais pas donner le code (car il ressemble à un devoirs à la maison pour moi), mais d'en expliquer quelques-uns des plus flagrantes erreurs qu'il a fait.
OriginalL'auteur Tural Gulmammadov | 2012-11-10
Vous devez vous connecter pour publier un commentaire.
Ce que vous faites n'est pas récursive, c'est itérative.
Récursive serait quelque chose comme:
En regardant l'historique de l'édition, j'ai eu
return -1
, ce qui signifie une feuille aurait une hauteur de 0 (ce qui est généralement la façon dont la hauteur d'un arbre est défini), mais l'OP spécifié "La hauteur d'un nœud feuille est de 1", de sorte que c'est probablement la raison pour laquelle je l'ai changé.Comment faites-vous la distinction entre la feuille et le nœud racine ici?
Un nœud feuille aura
None
pournode.left
etnode.right
, donc la fin de la récursivité là, il n'y a pas besoin de traiter de la feuille ou de l'intérieur ou de la racine des nœuds différemment.pour tout nœud de la hauteur est la hauteur de ce grand enfant de l'arbre (c'est ce que la fonction max) + 1. Pour un nœud feuille où les deux nœud.gauche et le nœud.la droite n'en sont pas hauteur sera de retour 0 pour les deux et la récursivité s'arrête là.
OriginalL'auteur mata
Vous avez eu la solution par mata, mais je vous suggère de regarder votre code et de comprendre ce qu'il fait:
Que cela fera? il va trouver le droit de l'enfant, son enfant, et ainsi de suite. Donc, ce vérifie une seule voie de la "droite" de la feuille.
Cela ne de même pour le gauche:
L'idée de récursivité, c'est que pour chaque subproblem, vous le résoudre en utilisant la même recette pour tous les autres sous-problèmes. Donc, si vous souhaitez appliquer votre algorithme uniquement à un sous-arbre ou une feuille, il fonctionne encore.
Aussi, une définition récursive s'appelle elle-même (bien que vous pouvez mettre en œuvre des ce avec une boucle, mais c'est au-delà de la portée ici).
Rappelez la définition:
La récursivité: voir la définition de la Récursivité.
😉
OriginalL'auteur Bitwise
Si vous considérez que chaque augmentation de bord à la hauteur.
Pour passer hackerrank cas de tests
OriginalL'auteur Shruti
Voici le programme complet en Python ::
Source : ici
OriginalL'auteur Akash Kandpal