英文:
I have a question on C++ recursive function
问题
这是获取二叉搜索树最大高度的函数：
int MaxHeight(BstNode* root) {
if (root == NULL) {
return -1;
}
return max(MaxHeight(root->left), MaxHeight(root->right)) + 1;
}
这个函数用来计算二叉搜索树的最大高度。如果传入的根节点是空的，它会返回-1。否则，它会递归地计算左子树和右子树的最大高度，然后返回较大者加1，以表示整棵树的高度。这个函数的核心思想是不断地向下递归，直到叶子节点，然后从叶子节点开始不断向上返回并累加高度值，最终得到整棵树的最大高度。
英文:
I was watching youtube video of implementing Binary Search Tree and this is the function where I can get the maximum height of tree.
int MaxHeight(BstNode* root) {
if (root == NULL) {
return -1;
}
return max(MaxHeight(root->left),MaxHeight(root->right))+1;
}
I roughly get how this function get the height but not exactly.
I wonder how this function flows....
I thought as soon as the function gets to the end of the node it return -1 and it is incrementing to the root by 1?
答案1
得分: 3
如果你制作一个调用图，你可能会更好地理解这个问题：
正如你所看到的，B 的值是 0，因为我们有 max(-1, -1) + 1 == 0。你可以将这个应用到所有的值上，然后你会明白为什么函数被实现成这样。
让我们试着理解返回值：
return max(MaxHeight(root->left), MaxHeight(root->right)) + 1：这个返回的思想很简单，我们获取左分支和右分支的高度，哪个分支更长，我们就计数哪个。然后，我们将当前节点的高度加上，这就是为什么我们做max() + 1来计算当前节点的高度。return -1。在这种情况下，root不是一个有效的节点。这个返回值与另一个返回值结合使用。这里的思想是，只有一个节点的树应该高度为0。但是，由于前一个节点将高度加一，我们需要确保invalid_height + 1 == 0。在调用中，这会被翻译成max(-1, -1) + 1 == 0。
如果我们定义“只有一个节点的树的高度是1”，那么我们的返回值将是0而不是-1。
英文:
If you make a call graph you can probably understand this better:
As you can see the value of B is 0 because we have max(-1, -1) + 1 == 0. You can apply this for all the values and you'll see why the function is implemented like this.
Let's try to understand the returns:
-
return max(MaxHeight(root->left), MaxHeight(root->right)) + 1: The idea of this return is simple, we get the height of the left branch and the right branch and whoever branch is longer that is the one we count. Then, we add the height of the current node and that is why we domax() + 1to count the current node. -
return -1. In this caserootis not a valid node. This return value is combined with what the other return does. The idea here is that a tree with only one node should have height0. But, because the previous node adds one to the height we need to make sure thatinvalid_height + 1 == 0. This in the calls gets translated tomax(-1, -1) + 1 == 0.
If we defined "the height of a tree with a single node is 1" then our return value would be0instead of-1.
答案2
得分: 0
该函数的作者认为没有子节点的BstNode（即左右子节点为NULL）高度为零。他们通过将NULL节点视为高度为-1来实现这个想法。因此，当我们对没有子节点的BstNode（将其称为root节点）调用MaxHeight时，我们找到MaxHeight(root->left)（其计算结果为-1）和MaxHeight(root->right)（其计算结果也为-1）中的较大值，并加上一。因此我们返回0。
英文:
The author of the function considers a BstNode with no children (i.e. left and right children are NULL) to have a height of zero. They implemented this idea by considering a NULL node to have a height of -1. Thus, when we call MaxHeight on a BstNode (call this node root) with no children, we find the greater of MaxHeight(root->left) (which evaluates to -1) and MaxHeight(root->right) (which also evaluates to -1), and add one. Thus we return 0.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论