Meta 树路径拼数字求和：十进制累积与深链

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 节点值必须是单个0–9整数；每条root→leaf按顺序拼数，前导0允许但数值不变。
• 空树0，内部节点不能作为路径终点。只有编号的相同题引用用于合并，不引入额外合同。

解题路线

1. 状态prefix表示到父节点拼出的数，进入node后value=prefix×10+digit。leaf将value加answer，其他继续传给孩子。
2. 乘10不是加节点权重，112类路径和与129类拼数字虽然都是DFS但递推不同。迭代避免极深树递归限制。
3. 校验每个digit，若可能多位值，需乘10^位数并定义负数/前导0文本，不能仍乘10。

手动走一遍

根1下叶2/3形成12与13，总25；根0下叶5仅数值5而不是加0另算一条。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def sum_root_leaf_numbers(root):
    """Node values are single digits 0..9; each root-to-leaf path is one decimal number."""
    if root is None:return 0
    result=0;stack=[(root,0)]
    while stack:
        node,prefix=stack.pop()
        if not isinstance(node.val,int) or not 0<=node.val<=9:
            raise ValueError('single decimal digits required')
        value=prefix*10+node.val
        if node.left is None and node.right is None:result+=value
        if node.right is not None:stack.append((node.right,value))
        if node.left is not None:stack.append((node.left,value))
    return result

复杂度

按节点计O(n)遍历、O(h)DFS栈，但深度h的拼数位长O(h)，大整数乘10/累加真实成本需按位数累计；固定宽度整数可能溢出。

易错点与追问

容易失分的边界

• 按普通节点相加会得到(1+2)+(1+3)=7而非25。
• 遍历所有节点都加prefix会把内部路径重复算。

继续深挖

• 若结果只需mod M，可每步prefix模M保持数值大小，leaf总和也模M。
• 若M=0或溢出需错误策略，不能利用wraparound作为未声明取模。