c# - 查找二叉树中叶到根路径的最大总和

Question

我创建了一个递归函数来计算二叉树的最大路径。我得到的反馈是它不起作用，但根据我的测试，它提供了正确的结果。有人能帮助我吗？

private long PathSum(int row, int column, Pyramid pyramid)
{
    // Base case, stop recurse when first row is reached.
    if (row == 0) return pyramid[row, column];

    // Set level to the current cell and add to the end result.
    long value = pyramid[row, column];

    // Continue to the next row.
    if (row != 0)
    {
        // Continue to the next left level.
        long left = pyramid[row - 1, column];

        // Continue to the next right level.
        long right = pyramid[row - 1, column + 1];

        // Get the highest of the left and right.
        long highest = Math.Max(left, right);

        // Get the index of the hightest path.
        int nextColumn = highest == left ? column : column + 1;

        // Recurse to the next level and add results together.
        value += GetTotal(row – 1, nextColumn, pyramid);
    }
    // Return result to the caller.
    return value;
}

Answer 1

您的算法存在一个严重错误:您只遍历“金字塔”一次，然后根据下一个结果选择基本案例，而没有查看底层节点。 为了说明您正在做什么，请考虑以下金字塔:

     1
   2   3
311  6    3

假设从1开始，将执行以下内容:

1. 查看底层节点的最大值(2 和 3)。
2. 向下移动到下一个节点 (3) 并重复。

您的算法将返回 10 (1 + 3 + 6)，而我的示例中的最大值是 311 + 2 + 1，因为它不会向前看。

您需要一种策略来向前迈进一步，以确定最佳路径。

编辑:查看Euler project #18 approach获取更多提示。