Meta 全部根到叶路径和：累积状态与输出顺序

题目重点：返回每条root-to-leaf路径的数值和，区别于目标和判定和任意路径最大和。

题意与假设

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

节点值可负，叶为left/right都空；空树返回[]。训练输出按左侧叶到右侧叶顺序。
每条路径一个sum，同和不同叶仍分别输出，不去重。

解题路线

栈携(node,rootToNodeSum)，进入孩子加其值；只有到leaf才append，不在每个内部节点输出。
LIFO栈先push右再左，保证左子树先处理；若题目不要求顺序也可任意，但训练显式固定。
不复制全部路径数组，只携当前累积和；输出所有sum所需空间O(numberOfLeaves)，完整路径文本则有额外总路径长度。

手动走一遍

根1，左2为叶，右3下左4/右5，返回[3,8,9]；根本身不是叶时不输出1。只有根7时返回[7]。

Python 参考实现

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

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

def root_leaf_sums(root):
    """Left-to-right leaf order; empty tree returns []."""
    if root is None:return []
    answer=[];stack=[(root,root.val)]
    while stack:
        node,total=stack.pop()
        if node.left is None and node.right is None:answer.append(total)
        if node.right is not None:stack.append((node.right,total+node.right.val))
        if node.left is not None:stack.append((node.left,total+node.left.val))
    return answer

复杂度

O(n)时间，DFS栈O(h)一般上界O(n)，输出O(L)叶数；整数位长若随深度增大需考虑算术成本。

易错点与追问

容易失分的边界

用target sum早停会漏掉其余叶路径，当前题需要全部输出。
共享全局sum回溯没有还原会污染兄弟支，携独立sum避免此错误。

继续深挖

若输出路径节点列表，每条叶路径需保存/复制，复杂度加入总输出长度，不再只O(n)。
同时返回min/max/count/average路径和可只聚合叶sum，不存全部结果。