在二叉搜索树中寻找高度
在二叉搜索树中寻找高度
提问于 2010-04-08 12:47:37
我想知道是否有人可以帮我修改这个方法来找到二叉树的高度。到目前为止，我的代码如下所示。然而，我得到的答案是比实际高度大1。但是当我从我的return语句中删除+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;
}
}回答 19
Stack Overflow用户
回答已采纳
发布于 2010-04-08 13:26:01
问题出在你的基本情况上。
“树的高度是从根到树中最深节点的路径长度。只有一个节点(根)的(根)树的高度为零。”- Wikipedia
如果没有节点，您希望返回-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;
}
}Stack Overflow用户
发布于 2010-04-08 13:08:46
二叉树的高度等于number of layers - 1。
请参阅http://en.wikipedia.org/wiki/Binary_tree上的图表
您的递归很好，所以只需在根级别减去1即可。
另请注意，您可以通过处理空节点来清理函数：
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}Stack Overflow用户
发布于 2014-09-25 13:20:38
int getHeight(Node node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2597637
复制相关文章
相似问题