DFS二叉树问题：yield与return的差异及return返回错误结果的原因

一、yield版本的正确逻辑 #

你写的yield版本是生成器函数，会按DFS顺序逐个输出叶子节点的值：

• 遇到叶子节点时，用yield node.val输出当前值，函数暂停执行
• 接着继续遍历左子树，把左子树的所有叶子逐个yield出来
• 再遍历右子树，把右子树的所有叶子逐个yield出来
• 最终调用dfs(root1)会得到包含所有叶子的迭代器，比如root1的叶子序列是2,3，root2的是3,2
• itertools.zip_longest会逐个对比两个迭代器的元素，第一个元素2≠3，直接返回False，结果正确

二、return版本的错误根源 #

当你把yield node.val改成return node.val后，DFS函数的逻辑完全偏离预期：

• 遇到叶子节点时，直接返回当前节点值，函数立即终止
• 对于非叶子节点（比如根节点1），调用dfs(node.left)会返回叶子值2，但这个返回值没有被收集；接着调用dfs(node.right)返回3，同样被丢弃
• 因为非叶子节点的DFS函数没有显式return语句，所以默认返回None
• 最终dfs(root1)和dfs(root2)的返回值都是None，比较None == None自然得到错误的True结果

补充：用return实现正确逻辑的写法 #

如果非要用return收集叶子，需要让DFS函数返回叶子列表，合并左右子树的结果：

def dfs(node):
    if not node:
        return []
    if not node.left and not node.right:
        return [node.val]
    # 合并左右子树的叶子列表
    return dfs(node.left) + dfs(node.right)

这样dfs(root1)会返回[2,3]，dfs(root2)返回[3,2]，直接比较两个列表就能得到正确结果。

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