给出以下代码:
private int getHeight(Node root){
if(root == null){
return 0;
}
else{
int leftHeight = getHeight(root.leftChild);
int rightHeight = getHeight(root.rightChild);
if(leftHeight > rightHeight){
return leftHeight + 1;
}
else{
return rightHeight + 1;
}
}
}
我不明白的是这两行:
int leftHeight = getHeight(root.leftChild);
int rightHeight = getHeight(root.rightChild);
它如何递归计算树的高度?如果一棵树看起来像这样:
4
/ \
/ \
1 9
\ /
\ 8
2
\
\
3
这两行如何计算呢?在地球上,递归如何增加1
?
我的看法是:
int leftHeight = getHeight(root.leftChild);
前往节点1
并在此处停止。
int rightHeight = getHeight(root.rightChild);
前往节点9
并在此处停止。
我只是不明白它是如何遍历整个事情的。
详细的解释会很棒!谢谢!
让我们首先总结一下我们拥有的元素。
停止条件
if(root == null){
return 0;
}
这意味着我们正在一个不存在的孩子上。例如,在您的树中,“ 2”元素的确有一个右孩子,但没有一个左孩子。所以什么时候你会打电话
int leftHeight = getHeight(root.leftChild);
root.leftChild将等于null。所以我们必须返回0,因为这个孩子不存在。
递归性
int leftHeight = getHeight(root.leftChild);
int rightHeight = getHeight(root.rightChild);
对于树中的每个元素,您想要获取其左侧和右侧之前的元素数量。因此,您要调用相同的函数,并在参数中输入左子项或右子项。如果该元素不存在,则输入stop条件,并返回0。如果有一个元素,我们要检查相同的事物,并以相同的方式继续。这就解释了为什么您不仅可以停在“ 1”和“ 9”,而且可以继续直到遇到一片叶子。
高度计算
if(leftHeight > rightHeight){
return leftHeight + 1;
}
else{
return rightHeight + 1;
}
我们要计算树的高度。我们之前曾解释过,leftHeight将在其左侧的实际元素下方包含元素数量,而在其右侧则包含rightHeight。如果左侧有更多元素,则意味着左侧的高度大于右侧的高度。然后,我们返回此计算出的高度,并将其加1。我们加1是因为我们所在的元素也是该高度的一部分:我们要告诉父元素,其下的高度是其子级(1),加上其子级下的所有元素。
例子
现在,我们已经解释了所有内容,让我们尝试使用您的树示例。
该函数将在“ 4”元素上调用,然后一直到达树的底部。让我们从“ 3”元素开始。因为它的左边或右边没有子元素,所以leftHeight和rightHeight等于0。这意味着该元素下的高度为0。然后我们只返回1,对应于“ 3”元素。
3
然后我们到达“ 2”。“ 2”在其左侧没有子代,因此leftHeight将等于0。但是rightChild将等于1,因为“ 3”元素返回了此信息。1> 0,因此我们将返回rightChild(1)的值,并为“ 2”元素添加一个。
2
\
\
3
然后,我们到达“ 1”元素。同样的概念:左边没有孩子,右边是1。leftHeight等于0,rightHeight等于2,因为“ 2”元素返回了此信息。2> 0,因此我们将返回rightChild(2)的值,并为“ 1”元素添加一个。
1
\
\
2
\
\
3
现在让我们走到另一边。我们有“ 8”元素。它没有子元素,其作用类似于“ 3”元素。然后,它将自己返回0 +1。
1
\
\ 8
2
\
\
3
“ 8”的父元素是“ 9”。此元素在右侧没有子元素,因此rightHeight将为0。但是在左侧有一个子元素“ 8”,该子元素返回他1。1> 0,因此我们将返回leftChild(1)的值,并且加9。
1 9
\ /
\ 8
2
\
\
3
然后,我们得出最后一个元素“ 4”。它的右边有一个孩子“ 9”,左边有一个孩子“ 1”。rightHeight将在那里为2,因为“ 9”返回了该值。leftHeight将为3,因为“ 1”返回了该值。3> 2,因此我们将返回leftHeight(3)的值,并为“ 4”元素添加一个。
4
/ \
/ \
1 9
\ /
\ 8
2
\
\
3
“ 4”是树的根元素,首次在其上调用了函数。最后,我们知道您的树的高度为4。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句