二分探索木における高さの求め方

質問

私は誰かがバイナリ検索ツリーの高さを見つけるためにこのメソッドを作り直すのを助けることができればと思っていた。今のところ、私のコードは次のようになります。しかし、私が得ている答えは、実際の高さよりも1だけ大きいです。しかし、私が私の戻り値文から+1を削除すると、それは実際の高さよりも1だけ小さくなります。どんな助けでも大いに感謝します。

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;
    }
}

どのように解決するのですか？

問題は、あなたのベースケースにあります。

"木の高さは、ルートから木の最深部のノードまでのパスの長さです。ノード (ルート) のみを持つ (根付きの) 木は、高さが 0 になります。 ウィキペディア

ノードがない場合は、0ではなく-1を返したい。 これは、最後に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;
    }
}