二叉搜索树中序遍历：while循环为何引发无限递归？

错误原因 #

你用while(self.left != None)的写法会触发无限递归——每次调用self.left.Inorder(vals)后，当前节点的self.left并没有被修改，循环条件始终成立，导致反复调用同一个左节点的Inorder方法，陷入死循环。

举个实际场景：当根节点是20，左子节点是6时，调用20的Inorder方法会进入while循环，执行6的Inorder方法。6的Inorder执行完毕返回后，回到20的while循环，此时self.left依然是6，条件仍为真，于是再次调用6的Inorder，无限重复这个过程。

换成if(self.left != None)就正常，因为if只会执行一次左节点的递归调用，之后就继续执行当前节点的后续逻辑，完全符合中序遍历“左子树→根节点→右子树”的顺序。

修正后的Inorder方法 #

def Inorder(self, vals):
    if self.left is not None:
        print("Going left value seen = ", self.left.val)
        self.left.Inorder(vals)
    vals.append(self.val)
    print("vals=", vals)
    if self.right is not None:
        print("Going right value seen = ", self.right.val)
        self.right.Inorder(vals)
    return vals

测试结果 #

运行你的测试代码后，输出的vals结果为[6, 20, 35]，完全符合二叉搜索树中序遍历的升序特性。

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