在二叉搜索树中查找高度 [英] Finding height in Binary Search Tree

问题描述

我想知道是否有人可以帮助我重新设计这个方法来找到二叉搜索树的高度.到目前为止，我的代码看起来像这样.但是，我得到的答案比实际高度大 1.但是当我从返回语句中删除 +1 时，它比实际高度小 1.我仍然试图用这些 BST.任何帮助将不胜感激.

I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But when I remove the +1 from my return statements, it's less than the actual height by 1. I'm still trying to wrap my head around recursion with these BST. Any help would be much appreciated.

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

推荐答案

问题在于您的基本情况.

The problem lies in your base case.

树的高度是从根到树中最深节点的路径长度.只有一个节点(根)的(有根)树的高度为零."- 维基百科

"The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero." - Wikipedia

如果没有节点，你想返回-1而不是0.这是因为你在最后加了1.

If there is no node, you want to return -1 not 0. This is because you are adding 1 at the end.

因此，如果没有节点，则返回 -1 以抵消 +1.

So if there isn't a node, you return -1 which cancels out the +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;
    }
}

这篇关于在二叉搜索树中查找高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！