Produto de todos os nós, exceto para um em árvore binária

Question

Suponha que nos recebemos uma árvore binária com um inteiro sentado em cada nó.Eu estou procurando uma maneira eficiente de encontrar para cada caminho da raiz para uma folha de cada produto possível com exatamente um nó omitido.Eu estou procurando uma solução sem divisões (i.e. inteiros podem ser zero).

Uma maneira de ir sobre isso eu pensei que é Eu posso calcular todos os produtos parciais possíveis que começam na raiz.Esse é cada nó armazena o produto do caminho exclusivo da raiz deste nó (mas exceto o inteiro armazenado a esse valor específico).Em seguida, para cada nó da folha, posso subir o caminho para o nó raiz multiplicando os inteiros no caminho.Em um determinado nó antes de acumular o nó no produto, posso multiplicar o produto com o produto prefixo armazenado no nó.

Parece que estou fazendo muitas multiplicações redundantes ao visitar cada caminho de uma folha para a raiz, uma vez que esses caminhos compartilham muitos nós.Existe uma maneira mais rápida de fazer isso?

Answer 1

uma abordagem simples: para um nó interno $ x $ , deixe $ p (x) $ denotar o produto dos inteiros no caminho da raiz para $ x $ e deixe $ Q (x) $ < / span> denotam o conjunto de inteiros obtidos como o produto de todos, exceto um dos inteiros no caminho da raiz para $ x $ . Agora, desce a árvore da raiz até as folhas, computando $ p (x) $ e $ Q (x) $ para cada nó $ x $ como você vai. Observe que você pode calcular $ p (x), q (x) $ de $ p (W), Q (W) $ , onde $ W $ é o pai da $ x $ .

O tempo de execução asictótico pior caso será $ O (n ^ 2) $ . Nenhum algoritmo tem melhor tempo de execução assintótico do pior caso, como pode haver $ \ theta (n ^ 2) $ produtos diferentes que você precisa para a saída, então qualquer algoritmo correto precisará ter tempo de execução de pior caso pelo menos $ \ theta (n ^ 2) $ .