寻找二叉树的深度

Question

我无法理解这个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.如果有一个包含3个左子节点的bst,则int lchild将返回3.而额外的+ 1是根节点.所以我的问题是,所有这些+1来自哪里.它在最后一个节点返回0,但为什么它在左/右子节点上升时返回0 + 1等？我不明白为什么.我知道它做到了,但为什么呢？

Answer 1

考虑这部分(更大的树):

       A
        \
         B

现在我们要计算这个treepart的深度,所以我们将指针传递给A它的param.

显然指针A不是NULL,所以代码必须:

• 呼唤maxDepth每个A孩子(左右分支).A->right是B,但A->left显然NULL(因为A没有左分支)

• 比较这些,选择最大的价值

• 返回此选择值+ 1(因为A它本身需要一个级别,不是吗？)

现在,我们要看看如何maxDepth(NULL)和maxDepth(B)计算.

前者非常简单:第一次检查将maxDepth返回0.如果另一个孩子NULL也是,两个深度都相等(0),我们必须为A自己返回0 + 1 .

但B不是空的; 但它没有分支,所以(正如我们注意到的)它的深度为1(NULL两个部分的s 最大为0 ,B自身为1 ).

现在让我们回过头来A.maxDepth它的左分支(NULL)是0,maxDepth它的右分支是1.这些中的最大值是1,我们必须为A它自己加1 - 所以它是2.

关键是当A只是大树的一部分时要完成的步骤; 计算结果(2)将用于更高级别的maxDepth呼叫.

Answer 2

使用前一个节点+ 1计算深度