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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (13)

我想知道是否有人可以帮我修改这个方法来找到二叉搜索树的高度。到目前为止,我的代码看起来像这样。但是,我得到的答案比实际高度大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;
    }
}
提问于
用户回答回答于

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

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);
用户回答回答于

二叉搜索树的高度等于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));
}

所属标签

可能回答问题的人

  • 天使的炫翼

    15 粉丝531 提问35 回答
  • 旺仔小小鹿

    社区 · 运营 (已认证)

    48 粉丝0 提问27 回答
  • 富有想象力的人

    2 粉丝0 提问26 回答
  • 发条丶魔灵1

    6 粉丝525 提问25 回答

扫码关注云+社区

领取腾讯云代金券