algorithm - 在二进制搜索树中查找高度

我想知道是否有人可以帮助我重做这种方法来找到二叉搜索树的高度。到目前为止，我的代码看起来像这样。但是，我得到的答案比实际高度大1。但是，当我从return语句中删除+1时，它比实际高度小1。我仍在尝试用这些BST。任何帮助将非常感激。

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}

最佳答案

问题出在您的基本情况上。

“树的高度是指从根到树中最深节点的路径的长度。只有一个节点(根)的(根)树的高度为零。” -Wikipedia

如果没有节点，则要返回-1而不是0。这是因为最后要加1。

因此，如果没有节点，则返回-1，这将抵消+1。

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}