如何检查二进制搜索树在Java中是否高度平衡

Question

 public boolean isBalanced() {
    return isBalanced(root);
}
private boolean isBalanced(BinaryNode<T> rootNode) {
    if (rootNode == null) {
        return true;
    }
    int left = rootNode.getLeftChild().getHeight();
    int right = rootNode.getRightChild().getHeight();
    if (left - right <= 1 || left - right >= -1) {
        if (isBalanced(rootNode.getLeftChild()) && isBalanced(rootNode.getRightChild())) {
            return true;
        }
    }

    return false;
}

我无法分辨这段代码出了什么问题，我不断收到空指针异常。我不确定要使其生效需要进行哪些更改。

Answer 1

我无法发表评论以询问您如何构造树的示例，但是，查看您的代码，我怀疑您有一个或多个没有左或右子级的BinaryNodes 。您可以使用类似于下面的代码进行检查。

int left = Objects.isNull(rootNode.getLeftChild()) ? 0 : rootNode.getLeftChild.getHeight();
int right = Objects.isNull(rootNode.getRightChild()) ? 0 : rootNode.getRightChild.getHeight();