澄清

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) 
} 

希望它有帮助！