我在理解此maxDepth代码时遇到了麻烦。任何帮助，将不胜感激。这是我遵循的摘录示例。
int maxDepth(Node *&temp)
{
if(temp == NULL)
return 0;
else
{
int lchild = maxDepth(temp->left);
int rchild = maxDepth(temp->right);
if(lchild <= rchild)
return rchild+1;
else
return lchild+1;
}
}
基本上，我的理解是该函数递归调用自身(对于每种左右情况)，直到到达最后一个节点。一旦执行，则返回0，然后执行0 + 1。那么前一个节点是1 + 1。那么下一个是2 + 1。如果bst有3个左子元素，则in lchild将返回3。多余的+ 1是根。所以我的问题是，所有这些+1都来自哪里。它在最后一个节点返回0，但是为什么它在左/右子节点向上返回0 + 1等？我不明白为什么。我知道这样做，但是为什么呢？
最佳答案
请记住，在二叉树中，一个节点最多有2个子节点(左右)
它是一种递归算法，因此会不断地调用自身。
如果temp(正在查看的节点)为null，则返回0，因为该节点为空，不应计数。这是基本情况。
如果正在查看的节点不为空，则它可能有子节点。因此它获得左侧子树的最大深度(对于当前节点的级别加1)和右侧子树(对于当前节点的级别加1)。然后比较两者并返回两者中的较大者。
它向下钻入两个子树(temp-> left和temp-> right)，并重复该操作，直到到达没有子节点的节点为止。到那时，它将在左右调用maxDepth，该参数将为null并返回0，然后开始返回上级调用链。
因此，如果您有一个由三个节点组成的链(例如，root-left1-left2)，它将下降到left2并调用maxDepth(left)和maxDepth(right)。每个返回0(它们为null)。然后回到左2。它比较，两者均为0，所以两者中的较大者当然为0。它返回0 + 1。然后我们在left1处-重复，发现1是它的左边n右边的较大者(也许它们相同或没有右边的 child )，因此它返回1 + 1。现在我们从根本上说，它返回2 + 1 = 3，即深度。