树中总和最高的路径

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

有关良好的解释，您可以从此处参考

Answer 2

你的错误应该是这样的：

sum = path.getChildren（）.get（i）.getValue（） findBestPath（path.getChildren（）.get（i））;

你必须写：

sum = path.getValue（） findBestPath（path.getChildren（）.get（i））;

你也不需要中间的“其他如果”，这是对于路径只有一个孩子的情况，“其他”在只有一个孩子的情况下也可以正常工作。

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

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;
    }
}

只有当所有值都是正数时，两者才有效。