java - 如何检查二叉搜索树是否完全平衡？

Question

我有这个家庭作业问题，并且我已经完成了除这个 isPerfectlyBalanced() 之外的所有方法。

我的所有测试都通过了，除了一个应该返回 false 但却返回 true 的测试。我已附上我当前的代码和失败的测试。任何关于如何解决这个问题的描述，甚至让我知道我的代码哪里错了，我们都将不胜感激!

private boolean isPerfectlyBalanced(Node node) {

    if (node == null) {
        return true;
    }

    if(size(node.left) == size(node.right)) {
        return true;
    }
    isPerfectlyBalanced(node.left);
    isPerfectlyBalanced(node.right);
    return false;

}


public boolean isPerfectlyBalancedS() {
    // TODO
    if (root == null) {
        return true;
    }
    return isPerfectlyBalanced(root);

}

这是我失败的测试:

assertFalse(set.isPerfectlyBalancedS());

谢谢!

我的尺码方法:

private int size(Node node){
    if (node == null){
        return 0;
    } else {
        return (size(node.left) + 1 + size(node.right));
    }
}
public int size() {
    // TODO
    return size(root);
}

Answer 1

在第一个方法的最后一行，您可能想要执行以下操作:

return (isPerfectlyBalanced(node.left) && isPerfectlyBalanced(node.right));

而不是

isPerfectlyBalanced(node.left);
isPerfectlyBalanced(node.right);
return false;

在您的代码中，您忽略子树上 isPerfectlyBalanced 的结果并始终返回 false。