java - 树中总和最大的路径

Question

我必须找到从根节点到叶节点的最大总和。我提出了以下节点，但它没有给出正确的输出。该树可以有 2 个以上的子节点(它不是二叉树)。

public static long findBestPath(Path path) {
    long max = 0, sum = 0;
    if (path.getChildren().size() == 0)
        return path.getValue();
    else if (path.getChildren().size() == 1)
        return path.getValue() + findBestPath(path.getChildren().get(0));
    else {
        for (int i = 0; i < path.getChildren().size(); i++) {
            sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i));
            if (sum > max)
                max = sum;
        }
        return max;
    }
}

我使用了另一种方法来解决我的问题。虽然知道正确的解决方案来找到非二叉树的最大总和的路径会很好。

Answer 1

你的错误应该在这一行:

sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i));

你必须写:

sum = path.getValue() + findBestPath(path.getChildren().get(i));

此外，您不需要中间的“else if”，这是针对路径只有一个子级的情况，“else”也适用于只有一个子级的情况。

所以你的代码应该是这样的:

public static long findBestPath(Path path) {
    long max = 0, sum = 0;
    if (path.getChildren().size() == 0)
        return path.getValue();
    else {
        for (int i = 0; i < path.getChildren().size(); i++) {
            sum = path.getValue() + findBestPath(path.getChildren().get(i));
            if (sum > max)
                max = sum;
        }
        return max;
    }
}

希望它能起作用。

另一个解决方案，返回 child(i) 的总和 + child(i) 的子级的最大总和(如果我理解正确的话)，将是:

public static long findBestPath(Path path) {
    long max = 0, sum = 0;
    if (path.getChildren().size() == 0)
        return 0;
    else {
        for (int i = 0; i < path.getChildren().size(); i++) {
            sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i));
            if (sum > max)
                max = sum;
        }
        return max;
    }
}

仅当所有值均为正数时，两者才有效。