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

