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

问题描述

我想知道是否有人可以帮助我重做这种方法以找到二叉搜索树的高度.到目前为止，我的代码看起来像这样.但是，我得到的答案比实际高度大1.但是，当我从return语句中删除+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屋！