根到叶子路径和算法Bug排查：递归累计和未正确递增问题

兄弟，我一眼就瞅出你代码里累计和不递增的核心问题了——你在递归调用左右子节点时，一直传递的是初始的node_data（也就是running_sum=0的那个），完全没把当前节点的值加到累计和里传给子节点！这就导致每一层递归都从0开始算，累计自然涨不上去。咱们一步步拆解问题：

你的代码里的关键错误 #

1. 递归顺序颠倒：你先递归了左右子树，才去计算new_running_sum，这时候这个值只和当前节点+初始0有关，和子树的递归完全脱节，等于白算。
2. 传递错误的累计和：调用root_to_leaf_helper(node.left, node_data)时，node_data还是父节点传进来的原始值，没有加上当前节点的node.val，子节点根本不知道父节点的存在，当然累计和一直是0加自己的值。
3. 缺少叶子节点判断：你原本的逻辑会把非叶子节点的路径也算进去，不过你已经意识到这点，咱们先聚焦累计和的问题。

修正后的思路（保留named tuple版本） #

核心就是：先更新当前节点的累计和，再把更新后的数据传给子节点递归，同时加上叶子节点的判断（符合题目要求的根到叶子路径）。

import collections

def root_to_leaf(target_sum, tree):
    NodeData = collections.namedtuple('NodeData', ['running_sum', 'num_found'])
    def root_to_leaf_helper(node, node_data):
        if not node:
            return NodeData(node_data.running_sum, False)
        
        # 第一步：把当前节点值加到累计和里，得到新的累计值
        new_running_sum = node.val + node_data.running_sum
        
        # 如果是叶子节点，直接判断是否符合目标和
        if not node.left and not node.right:
            return NodeData(new_running_sum, new_running_sum == target_sum)
        
        # 如果已经找到符合条件的路径，直接返回结果
        if node_data.num_found:
            return NodeData(new_running_sum, True)
        
        # 递归左子树，传递更新后的累计和与状态
        left_check = root_to_leaf_helper(node.left, NodeData(new_running_sum, node_data.num_found))
        if left_check.num_found:
            return left_check
        
        # 递归右子树，传递左子树的状态（左已经找到的话右不用再跑）
        right_check = root_to_leaf_helper(node.right, left_check)
        return right_check
    
    return root_to_leaf_helper(tree, NodeData(0, False)).num_found

更简洁的版本（不用named tuple） #

其实这个场景下，用named tuple有点冗余，直接传递累计和+返回布尔值更清晰：

def root_to_leaf(target_sum, tree):
    def helper(node, current_sum):
        if not node:
            return False
        
        # 更新当前累计和
        current_sum += node.val
        
        # 叶子节点判断：当前和是否等于目标
        if not node.left and not node.right:
            return current_sum == target_sum
        
        # 递归左右子树，只要有一个找到就返回True
        return helper(node.left, current_sum) or helper(node.right, current_sum)
    
    return helper(tree, 0)

为什么之前的累计和永远上不去？ #

举个简单例子：假设树是根节点(1) -> 左叶子(2)，目标和3。你的原始代码会先递归左叶子，传递的是running_sum=0，左叶子返回NodeData(2, False)，然后回到根节点计算new_running_sum=1+0=1，最后返回NodeData(1, False)——完全没把1和2加起来，因为左叶子的递归根本没拿到根节点的1！

修正后，根节点先算new_running_sum=1+0=1，传给左叶子，左叶子算2+1=3，刚好等于目标和，返回True，完美解决问题。

内容的提问来源于stack exchange，提问作者segue_segway