在二叉樹中查找最大總和葉根路徑

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