Diamètre de l'Arbre Binaire - Meilleure Conception
J'ai écrit un code pour trouver le diamètre de l'Arbre Binaire.
Besoin de suggestions pour la suite:
- Puis-je le faire sans utiliser de variable statique au niveau de la classe?
- Est l'algorithme fine/toutes les suggestions?
public class DiameterOfTree { public static int diameter = 0; public static int getDiameter(BinaryTreeNode root) { if (root != null) { int leftCount = getDiameter(root.getLeft()); int rightCount = getDiameter(root.getRight()); if (leftCount + rightCount > diameter) { diameter = leftCount + rightCount; System.out.println("---diameter------------->" + diameter); } if ( leftCount > rightCount) { return leftCount + 1; } return rightCount + 1; } return 0; } }
qu'entendez-vous par
arun, offcourse, j'ai testé le code. Je veux dire que peut-il y avoir un meilleur algorithme?
À cette question, aussi bien aller sur la Revue de Code.
merci. Na pas savoir à propos de la révision du code. Vais essayer.
Ohh ok. Veuillez vous référer à cette geeksforgeeks.org/archives/5687
is the algorithm fine?
. Avez-vous tester le code?arun, offcourse, j'ai testé le code. Je veux dire que peut-il y avoir un meilleur algorithme?
À cette question, aussi bien aller sur la Revue de Code.
merci. Na pas savoir à propos de la révision du code. Vais essayer.
Ohh ok. Veuillez vous référer à cette geeksforgeeks.org/archives/5687
OriginalL'auteur Manish | 2012-08-10
Vous devez vous connecter pour publier un commentaire.
Il y a trois cas à considérer lorsque vous essayez de trouver le plus long chemin entre deux nœuds dans un arbre binaire (diamètre):
Le plus long chemin à travers la racine est simplement la somme des hauteurs de la gauche et la droite sous-arbres + 1 (pour le nœud racine), et les deux autres peuvent être trouvées de manière récursive:
Quelle est la complexité de ce code O(n^2)?
Oui, c'est la complexité est O(n^2) qui se déplace à chaque fois jusqu'en bas pour trouver la hauteur. Je suis à la recherche pour le code qui calcule la hauteur en même traversée que le diamètre.
Vous êtes à la hauteur de mélange avec des nœuds, la hauteur est le nombre d'arêtes", donc un arbre avec un seul nœud a une hauteur de 0. techniquement, votre code est correct, mais pas dans la terminologie.
Selon ce code, le diamètre de cet arbre: a -> b -> c -> d est 4. Mais le seul nœud feuille est d'. Ainsi, le diamètre, qui est définie comme la longueur du plus long chemin entre les deux feuilles, devrait être de 1.
OriginalL'auteur verdesmarald
Ici est un O(n) solution avec un minimum de changements pour la accepté de répondre:
Juste calcule la hauteur et le diamètre à la même heure. Et, depuis Java n'a pas passé par référence j'ai défini un int[] pour retourner le résultat.
int[] rightResult = getDiameter(root.getLeft());
devrait probablement être:int[] rightResult = getDiameter(root.getRight());
?OriginalL'auteur Niki
Voici une solution en Java qui a
O(N)
temps de la complexité.Il calcule la hauteur de la même récursivité lors du calcul du diamètre.
Référence Lien
Salut @Che, la raison pour laquelle vous avez besoin d'une classe wrapper est parce que Java est le Passage Par Valeur ce qui signifie que l'utilisation d'un objet wrapper autour de vos données est la manière la plus simple pour maintenir correctement les valeurs par le biais de niveaux de récursivité. Voici un autre lien utile
Pour un arbre avec seulement 1 nœud, votre code vous donnera 1 du diamètre, ce qui est faux. Il devrait être 0 pour un tel cas.
Bien, 1 nœud de l'affaire pour laquelle vous pourriez vous dire 0 ou 1 pourrait être valide les réponses. Tout dépend si, dans votre définition du diamètre de vous, vous comptez le nœud de départ lorsque vous la calculer.
OriginalL'auteur nem035
Vous n'avez pas besoin de stocker le résultat dans le champ statique de diamètre. Simplement utiliser la méthode statique comme ça:
Vous avez raison, merci. J'ai fait la correction.
Pouvez-vous fournir le code pour la version optimisée qui calcule la hauteur en même récursivité comme diamètre, de sorte qu'il n'a pas à aller jusqu'en bas pour calculer la hauteur? De cette façon, c'est la complexité sera de O(n) O(n^2)
Vous pouvez échanger de temps pour l'espace et ajouter memoization pour le temps linéaire de la complexité (parce que chaque nœud de la hauteur peut être calculé à partir des résultats de ses sous-arbres dans
O(1)
temps). Alternativement, vous pouvez utiliser un post-ordre de la traversée (ce qui peut être fait de manière itérative au lieu d'utiliser la récursivité) et de stocker ces résultats.OriginalL'auteur Xavier Delamotte
Le diamètre d'un arbre T est
OriginalL'auteur Snehal Masne
Il y a un minimum de O(n) réponse par rapport à la accepté.
Assumer
diameter
est une variable statique dans la classe.Pourquoi êtes-vous à l'aide de
diameter
comme variable normale en argument d'une méthode?OriginalL'auteur shakirthow
OriginalL'auteur ChrisBangle
Soigné et propre solution:
OriginalL'auteur arora
Ici est une solution récursive en C++ qui vous donne de la hauteur ainsi que le diamètre de l'arbre binaire.
Le temps de la complexité de ce est O(h) où h est la hauteur de l'arbre.
Espérons que vous avez aidé.
OriginalL'auteur Rishab Dhawan