在二叉树中查找路径的最大乘积

Question

我需要一些帮助来想出一种算法来计算从二叉树的叶到根的任何路径上的值的最大乘积。到目前为止我有：

int max_path_prod_rec(Tree* t, int max_so_far, int path_prod) {
    if (is_leaf(t)) 
        return t->value;   

    int left = max_path_prod_rec(t->left, max_so_far, path_prod);
    int right = max_path_prod_rec(t->right, max_so_far, path_prod);

    if (left > right) 
        return left * t->value;
    else 
        return right * t->value;
}

int max_path_prod(Tree* t) {
    require("path product only defined for non-empty trees", t != NULL);
    return max_path_prod_rec(t, INT_MIN, 1);
}

问题是当连续有 2 个负数时此函数不起作用，例如 10 * (-3) * (-6)。我该如何改进？

编辑：示例：

    //   10
    //  2   5
    // 1 -3 4 -6
    t = node(node(leaf(1), 2, leaf(-3)), 10, node(leaf(4), 5, leaf(-6)));
    printf("%i\n", max_path_prod(t));

会return10 * 5 * 4 == 200。但是

    //   10
    //  2   -5
    // 1 -3 4 -6
    t = node(node(leaf(1), 2, leaf(-3)), 10, node(leaf(4), -5, leaf(-6)));
    printf("%i\n", max_path_prod(t));

Returns 10 * 2 * 1 == 20 而不是 10 * (-5) * (-6) == 300

Answer 1

一条路径的乘积只有当它的所有节点都被访问过并且没有部分路径是决定性的时才能知道。所以你必须遍历整棵树。安排一个标准的树遍历，但沿着部分路径跟踪产品，并在每个节点上更新迄今为止的最大值。

（您的解决方案过早地放弃了一些路径。）

一个简单的解决方案：

if (is_leaf(t))
    return t->value;
else
    return max(t->value * product(t->left), t->value * product(t->right));

Answer 2

基本问题是，在处理子树时，您需要考虑将子树结果合并到整个树的结果中时应用的符号更改。如果总体结果将是负数，那么您希望最小化绝对值；否则，您想最大化它。但是你可以知道这一点，事实上，你可以做得更好。

我不会为你写这个练习的解决方案，但你有一个合理的基础，我会尽力让你走上正确的道路。考虑您的函数签名：

int max_path_prod_rec(Tree* t, int max_so_far, int path_prod)

现在看看您对该功能的实现。您真的按照名称所暗示的方式使用 max_so_far 和 path_prod 吗？如果您更新函数以在递归时传递这些参数的正确值，会发生什么情况？它如何使用其中之一或两者来帮助它实现 objective?

Answer 3

在我看来，您应该编写一个更简单的例程（不需要将任何内容传递给子树，因为我们正在从叶到根构建产品）

int max_path_prod_rec(Tree* t)
{
    if (t == NULL) return 1;
    int left  = max_path_prod_rec(t->left);
    int right = max_path_prod_rec(t->right);
    return (left > right ? left : right) * t->value; 
}

在您的代码中：

int max_path_prod_rec(Tree* t, int max_so_far, int path_prod) {
    if (is_leaf(t)) /* you should have posted this function */
        return t->value;

到这里你是正确的（假设你永远不会将 NULL 引用传递给 t 参数）...


    int left  = max_path_prod_rec(t->left,  max_so_far, path_prod);
    int right = max_path_prod_rec(t->right, max_so_far, path_prod);

但这里您假设节点（如果它不是叶节点）将同时附加 children，但事实并非如此！你应该这样做，检查 children 是否只存在。


    if (left > right) 
        return left  * t->value;
    else 
        return right * t->value;
}

如果您已完成：

int max_path_prod_rec(Tree* t, int max_so_far, int path_prod) {
    if (t == NULL) 
        return 1; /* you add always an extra factor of 1, don't hurt */

    int left  = max_path_prod_rec(t->left,  max_so_far, path_prod);
    int right = max_path_prod_rec(t->right, max_so_far, path_prod);

    if (left > right) 
        return left * t->value;
    else 
        return right * t->value;
}

那么您的代码将受到保护，并且您的代码将导致（对于叶节点）children 为 1，并且返回值为 t->value * 1 * 1 ==> t->value

如果你想比较绝对值，只需这样做：

int max_path_prod_rec(Tree* t)
{
    if (t == NULL) return 1;
    int left  = t->value * max_path_prod_rec(t->left);
    int right = t->value * max_path_prod_rec(t->right);
    return abs(left) > abs(right)
              ? left
              : right; 
}

在二叉树中查找路径的最大乘积

Finding the maximum product of a path in binary tree

c

algorithm

binary-tree