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

Question

我想知道是否有人可以帮我修改这个方法来找到二叉搜索树的高度.到目前为止,我的代码看起来像这样.但是,我得到的答案比实际高度大1.然而当我从我的返回语句中删除+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;
    }
}

Answer 1

问题出在你的基础案例中.

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

如果没有节点,则要返回-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;
    }
}

Answer 2

二叉搜索树的高度等于number of layers - 1.

请参阅http://en.wikipedia.org/wiki/Binary_tree上的图表

你的递归是好的,所以只需在根级别减去一次.

另请注意,您可以通过处理空节点来清理函数:

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}

Answer 3

int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Answer 4

IMO,您的代码将受益于简化一点.当子指针为null时,不要尝试结束递归,而只在当前指针为空时结束它.这使得代码很多容易编写.在伪代码中,它看起来像这样:

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

Answer 5

class Solution{
    public static int getHeight(Node root) {
        int height = -1;

        if (root == null) {
            return height;
        } else {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }

Answer 6

对于像我这样喜欢单行解决方案的人：

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}