Produit de tous les nœuds sauf un dans un arbre binaire

Question

Supposons que nous recevons un arbre binaire avec un entier assis à chaque nœud.Je cherche un moyen efficace de trouver pour chaque chemin de la racine à une feuille de chaque produit possible avec exactement un noeud omis.Je cherche une solution sans divisions (c'est-à-dire des entiers peuvent être zéro).

Un moyen d'aller à ce sujet, je pensais être Je peux calculer tous les produits partiels possibles à partir de la racine.C'est chaque nœud stocke le produit du chemin unique à partir de la racine de ce nœud (mais à l'exception de l'entier stocké à cette valeur particulière).Ensuite, pour chaque nœud de feuille, je peux marcher sur le chemin du nœud racine multipliant les entiers sur le chemin.Sur un nœud donné avant d'accumuler le nœud dans le produit, je peux multiplier le produit avec le produit de préfixe stocké dans le nœud.

On se sent comme si je fais beaucoup de multiplications redondantes lors de la visite de chaque trajet d'une feuille à la racine, car ces chemins partagent potentiellement beaucoup de nœuds.Y a-t-il un moyen plus rapide de le faire?

Answer 1

Une approche simple: pour un nœud interne $ x $ , let $ p (x) $ Notez le produit des entiers sur le chemin de la racine à $ x $ et laissez $ q (x) $ < / Span> désigne l'ensemble d'entiers pouvant être obtenus comme le produit de tous sauf un des entiers sur le chemin de la racine à la racine à $ x $ . Maintenant, descendez l'arbre de la racine vers les feuilles, calculant $ p (x) $ et $ q (x) $ pour chaque nœud $ x $ comme vous allez. Notez que vous pouvez calculer $ p (x), q (x) $ de $ p (w), q (w ) $ , où $ w $ est le parent de $ x $

Le temps de fonctionnement des cas asymptotique sera $ o (n ^ 2) $ . Aucun algorithme n'a de meilleur temps de fonctionnement asymptotique au cas, car il peut y avoir $ \ theta (n ^ 2) $ différents produits que vous devez produire, donc tout algorithme correct aura besoin d'avoir le pire temps de fonctionnement au moins $ \ theta (n ^ 2) $ .