Python实现二叉搜索树(BST)递归高度计算方法结果错误排查

问题原因 #

你写的height方法存在两处核心逻辑错误：

• 终止条件判断逻辑错误：只要左/右任意一个子节点为None就直接返回1，完全忽略了另一个存在的子节点的高度，比如节点有左孩子但无右孩子的场景会被误判为叶子节点，直接返回高度1。
• self == None的判断完全无效：height是Node类的实例方法，只有Node实例可以调用该方法，self永远不可能为None。

修复后的代码 #

将原height方法替换为以下实现即可：

def height(self):
    # 左节点为空则左子树高度为0，否则递归计算左子树高度
    left_height = self.left.height() if self.left is not None else 0
    # 右节点为空则右子树高度为0，否则递归计算右子树高度
    right_height = self.right.height() if self.right is not None else 0
    # 当前节点高度为左右子树最大高度+1，符合要求：叶子节点（左右都为空）高度为1
    return max(left_height, right_height) + 1

验证效果 #

修复后所有测试用例均可通过：

• t2（节点12）高度为2，符合测试要求
• t4（节点40）插入26、33后高度为3，符合测试要求
• t1（根节点25）整体高度为4，符合预期

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