You need to enable JavaScript to run this app. Python二叉树中序遍历生成器异常问题排查与修正
优惠活动
大模型
产品
解决方案
定价
更多

Python二叉树中序遍历生成器异常问题排查与修正

二叉树中序生成器的问题修正

问题核心原因

你当前实现的遍历逻辑拿不到完整结果,根源是递归调用生成器时没有做迭代内容的透传:
生成器函数的特性是,只要函数体内存在yield,直接调用函数不会执行内部的遍历逻辑,只会返回一个空的生成器对象。你之前写的if root.left: self.traversal(root.left)、if root.right: self.traversal(root.right)两行代码,执行完只是生成了对应子树的遍历生成器,既没有触发子树的遍历流程,也没有把子树遍历产出的值传递到外层。
最终整个流程只会执行当前调用栈上的yield root.val,也就是根节点的数值,其余节点的遍历逻辑完全不会运行——这就是你之前调用时仅能拿到根节点1的原因。

补充说明:如果真的把traversal函数里的yield关键字移除,这个函数会变成无返回值的普通函数,此时再用next()读取结果会直接触发类型错误,根本不会得到[1]的输出,你之前遇到的仅返回1的情况,和是否保留yield没有直接关系。

具体调整方法

要让嵌套递归的生成器正常工作,需要用Python的yield from语法,将子生成器的所有迭代内容逐层透传到外层。修正后的traversal函数代码如下:

def traversal(self, root):
    if root.left:
        # 透传左子树遍历生成器的全部产出值
        yield from self.traversal(root.left)
        
    yield root.val
    
    if root.right:
        # 透传右子树遍历生成器的全部产出值
        yield from self.traversal(root.right)

如果不习惯用yield from,也可以通过手动遍历子生成器的方式实现等价效果,只是代码会更冗余:

def traversal(self, root):
    if root.left:
        for val in self.traversal(root.left):
            yield val
        
    yield root.val
    
    if root.right:
        for val in self.traversal(root.right):
            yield val

效果验证

针对你使用的层序输入[1,2,3,4,5,null,7],正确的中序遍历序列为[4,2,5,1,3,7]。修正代码后,在connect方法中连续三次调用next(reader),会依次拿到值4、2、5,和预期遍历逻辑完全一致。


内容的提问来源于stack exchange,提问作者abdullahDev

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.14 09:36:05