遞歸二叉樹最大路徑的呼叫解釋總和

Question

這就是問題所在：

給定一個二叉樹，找到最大路徑總和。

對於這個問題，路徑被定義爲從一些 起始節點到沿着父子 連接的樹中的任何節點的任何節點序列。路徑必須包含至少一個節點，並且不需要 來通過根。

例如：考慮到以下二叉樹，

1 
/\ 
2 3 

返回6.

此問題的遞歸解決方案是這樣的：

int max = Integer.MIN_VALUE; 

public int maxPathSum(TreeNode root) { 
    helper(root); 
    return max; 
} 

private int helper(TreeNode root) { 
    if (root == null) return 0; 
    int left = Math.max(helper(root.left), 0); 
    int right = Math.max(helper(root.right), 0); 
    max = Math.max(max, root.val + left + right); 
    return root.val + Math.max(left, right); 
} 

我們呼籲helper爲離開孩子，並檢查離開的孩子是否大於零。

然後我們稱helper爲正確的孩子，並檢查正確的孩子是否大於零。

然後我們檢查當前的max值與總和root.val + left + right - 這也很清楚。

但是，在回報聲明中，我們只有根值和其中一個孩子的總和。 爲什麼我們只有一個孩子在這裏，但如果他們都是積極的，他們不是兩個？

Answer 1

遞歸方法不返回解決方案本身，它只返回該部分的最大值。最終的解決方案是在最大變量中計算的。

如果您檢查maxPathSum方法，它返回的最大值不是從輔助方法返回的值。

這是因爲可能的是，該解決方案不接觸根，如這裏：

 0 
    / \ 
    1  0 
/\ /\ 
    2 3 0 0