澄清

Question

可能有人爲對這個問題的解決方案提供一種澄清的遞歸調用：

給出一個包含有從0-9只，每根到葉的數字 的二進制樹路徑可以代表一個數字。查找所有從根到葉 號碼的總和。

例如，對於此樹：

 1 
    /\ 
    2 3 
/ \ 
4  5 

的結果應該等於12 + 13 + 24 + 25

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

public int sum(TreeNode root) { 
    return helper(root, 0); 
} 

private int helper(TreeNode node, int sum){ 
    if(node == null) return 0; 
    sum = sum * 10 + node.val; 
    if(node.left == null && node.right == null) return sum; 
    return helper(node.left, sum) + helper(node.right, sum); 
} 

我想遵循方法helper的所有遞歸調用，並在每一步找出總和值。

例如，在第一步驟中可變sum等於0 * 10 + 1 = 1。然後我們稱之爲helper(node.left, 1)和sum對步驟等於1 * 10 + 2 = 12。然後，我們在該步驟上呼叫helper(node.left, 12)和sum等於12 * 10 + 4 = 124，這顯然是不正確的，因爲sum應該是24。

有人能解釋我的方法有什麼問題嗎？

Answer 1

試試這個（但我還優選124 + 125 + 13爲結果）：

public int sum(TreeNode root) { 
     if (root == null) return 0; 
     return sum(root, 0); 
} 

private int sum(TreeNode node, int parentValue){ 
     if(node == null) return 0; 
     return sum(node.left, node.val) + sum(node.right, node.val) + parentValue * 10 + node.val; 
} 

Answer 2

問題是您缺少的中間節點的數據和2位數據的限制。

刪除'if（node.left == null & & node.right == null）return sum;'，只發送父節點值到遞歸調用並添加當前節點數據。

DoctorLOL的解決方案几乎是正確的，您可能希望添加忽略根節點數據代碼。以下代碼可能會有幫助

public int sum(TreeNode root) { 
    return helper(root, -1); 
} 

private int helper(TreeNode node, int parentValue){ 
    if(node == null) return 0; 
    if (parentValue != -1) 
    return helper(node.left, node.val) + helper(node.right, node.val) + parentValue * 10 + node.val; 
    else 
    return helper(node.left, node.val) + helper(node.right, node.val) 
} 

希望它有幫助！