Producto de todos los nodos excepto uno en árbol binario.

Question

Supongamos que nos dan un árbol binario con un entero sentado en cada nodo.Estoy buscando una forma eficiente de encontrar para cada ruta de la raíz a una hoja, cada producto posible con exactamente un nodo omitido.Estoy buscando una solución sin divisiones (I.E. Los enteros pueden ser cero).

Una forma de ir sobre esto, pensé en es Puedo calcular todos los productos parciales posibles que comienzan en la raíz.Ese es que cada nodo almacena el producto de la ruta única desde la raíz de este nodo (pero excepto el entero almacenado en ese valor particular).Luego, para cada nodo de hoja, puedo subir el camino al nodo raíz que multiplican los enteros en el camino.En un nodo dado antes de acumular el nodo en el producto, puedo multiplicar el producto con el producto prefijo almacenado en el nodo.

Se siente como si estuviera haciendo muchas multiplicaciones redundantes al visitar cada ruta desde una hoja a la raíz, ya que estos caminos potencialmente comparten muchos nodos.¿Hay una manera más rápida de hacer esto?

Answer 1

Un enfoque simple: para un nodo interno $ x $ , deja $ P (x) $ denota el producto de los enteros en el camino desde la raíz a $ x $ y deja $ q (x) $ < / SPAN> Denote el conjunto de enteros que se pueden obtener como producto de todos menos uno de los enteros en la ruta de la raíz a $ x $ . Ahora, descienda el árbol de la raíz hasta las hojas, computando $ P (x) $ y $ q (x) $ para cada nodo $ x $ a medida que avanza. Tenga en cuenta que puede calcular $ P (x), q (x) $ de $ p (w), q (w ) $ , donde $ w $ es el padre de $ x $ .

El tiempo de ejecución asintótico en el peor de los casos será $ O (n ^ 2) $ . Ningún algoritmo tiene un mejor tiempo de funcionamiento asintótico en el peor, ya que puede haber $ \ theTa (n ^ 2) $ $ diferentes productos que necesita para generar, por lo que cualquier algoritmo correcto deberá tener el peor de los casos, al menos $ \ theTa (n ^ 2) $ .