我正在看youtube上实现二叉搜索树的视频，这是我可以得到树的最大高度的函数。
int MaxHeight(BstNode* root) { if (root == NULL) { return -1; } return max(MaxHeight(root->left),MaxHeight(root->right))+1;}
int MaxHeight(BstNode* root) {
if (root == NULL) {
return -1;
}
return max(MaxHeight(root->left),MaxHeight(root->right))+1;
我大概知道这个函数是如何得到高度的，但不完全是。我想知道这个函数是如何运行的....我认为函数一到达节点的末尾就返回-1，并且它会向根节点递增1？
nqwrtyyt1#
如果你做一个调用图，你可能会更好地理解这一点：
你可以看到，B的值是0，因为我们有max(-1, -1) + 1 == 0。你可以对所有的值应用这个方法，你就会明白为什么这个函数是这样实现的。让我们试着理解回报：
B
max(-1, -1) + 1 == 0
return max(MaxHeight(root->left), MaxHeight(root->right)) + 1
max() + 1
return -1
root
0
invalid_height + 1 == 0
如果我们定义 “一棵树只有一个节点的高度是1”，那么我们的返回值将是0而不是-1。
-1
p1tboqfb2#
函数的作者考虑没有子节点的BstNode（即左子和右子子是NULL）以具有零的高度。他们通过考虑NULL节点的高度为-1来实现这个想法。因此，当我们在没有子节点的BstNode上调用MaxHeight（调用此节点root）时，我们会找到MaxHeight（root->left）（其计算结果为-1）和MaxHeight（root->right）（其计算结果也为-1）中的较大者，并添加1。我们返回0。
NULL
2条答案
按热度按时间nqwrtyyt1#
如果你做一个调用图，你可能会更好地理解这一点：
你可以看到，
B的值是0，因为我们有max(-1, -1) + 1 == 0。你可以对所有的值应用这个方法，你就会明白为什么这个函数是这样实现的。让我们试着理解回报：
return max(MaxHeight(root->left), MaxHeight(root->right)) + 1：这个返回的想法很简单，我们得到左分支和右分支的高度，无论哪个分支更长，都是我们计数的分支。然后，我们将当前节点的高度相加，这就是为什么我们使用max() + 1来计算当前节点。return -1。在这种情况下，root不是有效节点。此返回值与其他返回值的作用组合在一起。这里的想法是，只有一个节点的树应该有高度0。但是，由于前一个节点将高度加1，因此我们需要确保invalid_height + 1 == 0。调用中的这个被转换为max(-1, -1) + 1 == 0。如果我们定义 “一棵树只有一个节点的高度是1”，那么我们的返回值将是
0而不是-1。p1tboqfb2#
函数的作者考虑没有子节点的BstNode（即左子和右子子是
NULL）以具有零的高度。他们通过考虑NULL节点的高度为-1来实现这个想法。因此，当我们在没有子节点的BstNode上调用MaxHeight（调用此节点root）时，我们会找到MaxHeight（root->left）（其计算结果为-1）和MaxHeight（root->right）（其计算结果也为-1）中的较大者，并添加1。我们返回0。