除了二进制树中的一个节点的产品

Question

假设我们被给出了一个二进制树，其中整数坐在每个节点处。我正在寻找一个有效的方法，可以找到从根到叶片的每一个路径，每种可能的产品都省略了一个节点。我正在寻找一个没有划分的解决方案（即整数可以为零）。

我想到的一种方式是 我可以计算从根目录开始的所有可能的部分产品。这是每个节点将唯一路径的乘积存储来自rootup此节点（但除了存储在该特定值的整数之外）。然后，对于每个叶节点，我可以向上行驶到乘以乘以整数的根节点的路径。在给定节点之前将节点累积到产品中，我可以将产品乘以存储在节点中的前缀产品。

感觉就像我在从叶子到root的每个路径时做了很多冗余乘法，因为这些路径可能分享大量节点。有没有办法更快地做到这一点？

Answer 1

一个简单的方法：对于内部节点 $ x $ ，let $ p（x）$ 将整数的乘以从根到 $ x $ ，并让 $ q（x）$ < / span>表示可以作为所有除了从根到 $ x $ 的路径上的所有整数的乘积的整数集合。现在，将树从根下降到叶子，计算 $ p（x）$ 和 $ q（x） $ 为每个节点 $ x $ 等等。请注意，您可以计算 $ p（x），q（x）$ from $ p（w），q（w ）$ ，其中 $ w $ 是 $ x $ 的父级。

渐近最差情况运行时间将是 $ o（n ^ 2）$ 。没有算法具有更好的最坏情况渐近运行时间，因为可以存在 $ \ theta（n ^ 2）$ 不同的产品，所以任何正确的算法需要具有最坏情况的运行时间至少 $ \ theta（n ^ 2）$ 。