Найти максимальную сумму листа в корневой путь в двоичном дереве

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 для получения дополнительных советов.

Answer 2

Я думаю, что вы описываете не двоичное дерево, а пирамиду чисел, и проблему лучше всего решить с помощью динамического программирования вместо обхода дерева. Вот пример кода для динамического программирования. Он не составлен, и я не знаю, например, C#:

private long DP(int maxRow, Pyramid pyramid) 
{ 
    int maxColumn = maxRow; 
    Pyramid result; 
    clear_pyramid(result); 
    for (int j=0; i<maxColumn; i++) { 
     result[0, j] = pyramid[0, j]; 
    }  
    for (int i=1; i<maxRow; i++) { 
     for (int j=0; j<maxColumn-i; j++) { 
      result[i,j] = Math.max(result[i-1,j], result[i-1,j+1]) + pyramid[i,j]; 
     }  
    } 
    return result[maxRow-1, 0]; 
}