二叉树路径和递归代码疑问：节点2遍历后为何执行pop？

代码实现 #

def path_sum(root,temp):
    print("root is",root)
    if root == None:
        return False
    temp.append(root.val)
    if root.left == None and root.right == None:
        if sum(temp) == targetSum:
            return True
    l=path_sum(root.left,temp)
    print("temp is",temp)
    r=path_sum(root.right,temp)
    temp.pop()
    return l or r

对应二叉树结构 #

1
/ \
2 3
  /
  4

疑问 #

调用path_sum(root.left,temp)递归处理节点2时，temp被更新为[1,2]，检查完路径和后返回。原本以为要先处理节点2的右子树才会执行pop，但实际运行中节点2遍历后就触发了pop，对此存在疑问。

原因拆解 #

我们一步步走节点2的完整递归流程：

1. 进入path_sum(2, [1])，执行temp.append(2)，temp变为[1,2]。
2. 节点2是叶子节点（左右子树都是None），先判断路径和是否等于targetSum，不管结果如何，接下来执行l=path_sum(root.left, temp)，也就是调用path_sum(None, [1,2])。
3. 进入空节点的递归，直接返回False，所以l的值是False。
4. 执行print("temp is",temp)，此时temp还是[1,2]。
5. 接着执行r=path_sum(root.right, temp)，也就是调用path_sum(None, [1,2])，同样返回False，r的值是False。
6. 走到temp.pop()，把2从temp中移除，temp变回[1]。
7. 最后返回l or r（也就是False），回到节点1的递归层。

你觉得“应该先处理右子树再pop”是正确的逻辑，但节点2的右子树本身就是空节点，对应的递归只是直接返回，没有额外的执行步骤，所以看起来像是处理完节点2就直接pop了——实际上pop是在处理完它的左右子树（包括两个空递归）之后才执行的，只是空递归没有输出，让你产生了“跳过右子树处理”的错觉。

举个对比：如果是节点3，它的左子树是4，那么会先递归处理节点4的整个流程（包括4的左右空递归、pop操作），等节点4的递归完全结束后，才会处理节点3的右子树（空递归），最后再执行节点3的pop。

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