如何检查二叉搜索树是否完全平衡？代码错误排查求助

你的isPerfectlyBalanced()方法逻辑存在两处关键错误，这就是导致测试用例失败的原因：

错误点拆解 #

1. 过早返回true，未递归验证子树
   你的代码中，只要当前节点的左右子树size相等就直接返回true，但完全没检查左右子树自身是否满足"完美平衡"的要求。比如测试用例中可能存在这样的树：根节点左右子树size相等，但左子树的某个节点左右size不等，这时候你的代码会直接返回true，但实际应该返回false。

2. 递归调用未利用返回值
   你调用了isPerfectlyBalanced(node.left)和isPerfectlyBalanced(node.right)，但完全没处理这两个调用的返回结果，最后直接返回false，这部分递归相当于无效执行，根本没起到验证子树的作用。

修正后的代码 #

private boolean isPerfectlyBalanced(Node node) {
    if (node == null) {
        return true;
    }
    // 首先检查当前节点的左右子树size是否相等
    if (size(node.left) != size(node.right)) {
        return false;
    }
    // 递归验证左右子树自身也必须是完美平衡的
    return isPerfectlyBalanced(node.left) && isPerfectlyBalanced(node.right);
}

逻辑说明 #

• 首先处理空节点的边界情况，空树视为完美平衡。
• 先判断当前节点的左右子树大小是否相等，如果不等直接返回false。
• 如果当前节点满足条件，必须递归检查左右子树是否也都满足完美平衡的要求，只有两者都返回true时，当前节点才返回true。

这样修改后，就能正确验证整棵树的每个节点是否都满足左右子树size相等的完美平衡条件，你的测试用例也会得到正确的false结果。

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