java - 有向无环图中的路径和

Question

给定一个有向无环图，确定是否有任何分支返回等于 22 的路径和。在下面的示例中，可以在 (7 + 8 + 3 + 4) 处找到这样的路径。这种算法的运行时间复杂度是多少？

      7  
     / \  
    8   6  
   / \ / \  
  2   3   8  
 /   /    \     
5   4      1  

这就是我想出来的。

public boolean hasPathToSum(Node root, int sum)
{
    if (root == null) return false;
    if (root.value == sum && (root.left == null && root.right == null))
        return true;

    return hasPathToSum(root.left, sum - root.value) || hasPathToSum(root.right, sum - root.value);
}

关于提高复杂性有更好的建议吗？

Answer 1

如果图中的所有值都是非负的，您可以使用 memoization 在 O((n + m) * sum) 中解决这个问题。在您的情况下，总和是固定的并且等于 22，因此解决方案实际上是线性的。

记忆化是一种不会两次计算相同值的技术。请注意，hasPathToSum(root, sum) 是一个纯函数:其结果仅取决于参数，没有副作用。这意味着我们可以将该函数的结果保存到某个映射 (root, sum) -> bool (可能是 Java 中的 HashMap 或 TreeMap，我不能准确地说，因为我不熟悉语言)。

现在，当调用该函数时，我们检查其参数是否出现在映射中。如果是，则返回保存的值。否则计算它，保存到 map 中并返回。这样，对于任何一组参数，该函数实际上只会计算一次。

最后一个优化仅适用于非负值。请注意，如果 x < 0，hasPathToSum(v, x) 的结果为 false。因此您可以进行截断:如果是这种情况，则立即返回 false。此优化确保对于每个节点，将使用最多 23 个不同的总和值调用 hasPathToSum，从而产生上述运行时间。