sujet:
Somme maximum de chemin maximum de l'arbre binaire
Étant donné un arbre binaire, trouvez la somme du chemin maximum.
Le chemin peut démarrer et se terminer à n'importe quel nœud de l'arbre.
Par exemple:
Compte tenu de l'arbre binaire ci-dessous,
1 / / 2 3
Retour 6.
Le nœud peut être négatif, à la recherche d'un plus grand chemin pour que les nœuds passent les plus importants. Le chemin peut démarrer et se terminer à n'importe quel nœud mais ne peut pas revenir en arrière.
Bien que cette question semble inhabituelle, si vous y pensez, vous constaterez que ce n'est rien de plus que la traversée des arbres binaires + des idées de planification dynamique simples.
Nous pouvons séparer le problème: même si le dernier plus grand chemin ne passe pas par le nœud racine, il doit avoir son propre "point le plus élevé". Par conséquent, nous n'avons qu'à découvrir tous les nœuds: si le chemin prend ce nœud comme "point le plus élevé", quelle est la longueur maximale du chemin? Remarque comme max. Trouvez ensuite la valeur maximale max dans Max, qui est le résultat que vous recherchez. La même idée que "trouver la plus grande subséquence continue dans une séquence entière".
Ce qui suit est de trouver la relation entre max correspondant à chaque "point le plus élevé".
Prenons le nœud racine comme exemple. La méthode de calcul pour le chemin maximum passant par le nœud racine est:
Nous trouvons la longueur maximale du chemin A dans le sous-arbre gauche avec l'enfant gauche comme point de départ, et la longueur maximale du chemin B dans le sous-arbre droit avec l'enfant droit comme point de départ. Puis le max = max de ce point (a + b + node.val, a + node.val, b + node.val, node.val)
Par conséquent, nous définissons une fonction pour calculer A ou B ci-dessus. Son paramètre est un nœud et sa valeur de retour est la longueur maximale du chemin. Cependant, le point de départ de ce chemin doit être le nœud d'entrée et le chemin doit être sur un sous-arbre avec le point de départ comme nœud racine.
Ensuite, la valeur de retour de la fonction func (nœud) peut être définie comme suit: returnmax (func (node.left) + node.val, func (node.right) + node.val, node.val)
La condition de terminaison est nœud == null, et il renvoie 0 directement.
Ensuite, nous avons constaté que le processus ci-dessus de calcul de la max et du calcul max peut être complètement mis dans Func (nœud).
Selon le code de cette idée, MaxPathSumcore est la mise en œuvre ci-dessus de Func (Node):
/ ** * Définition de l'arbre binaire * struct treenode {* int val; * Treenode * gauche; * Treenode * à droite; * Treenode (int x): val (x), gauche (null), droit (null) {} *}; * / class solution {public: int maxpathsum (Treenode * root) {maxPathSumcore (root); return max;} int maxpathSumcore (Treenode * node) {if (null == node) return 0; int a = maxpathsumcore (node -> gauche); int b = maxpathsumCore (node -> droit); if ((a + b + nœud-> val)> max) max = (a + b + nœud-> val); if ((a + nœud-> val)> max) max = (a + nœud-> val); if ((b + nœud-> val)> max) max = (b + node-> val); if (nœud-> val> max) max = nœud-> val); if (nœud-> Val> max) max = nœud-> val); if (nœud-> Val> max) max = nœud> Val; maxviatisnode = ((a + node-> val)> nœud-> val? (a + node-> val): node-> val); return (maxviatisnode> (b + node-> val)? maxviathisnode: (b + node-> val));} private: int max = -99999999;};La complexité du temps o (n), n est le nombre total de nœuds.
Résumer
Ce qui précède est l'intégralité du contenu de cet article sur l'analyse de code du chemin maximum de l'arbre binaire dans la programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!