2

我无法理解这个 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 等？我不明白为什么。我知道它会这样做，但为什么呢？

4

8 回答 8

8

考虑这部分（一棵更大的树）：

       A
        \
         B

现在我们要计算这个树部分的深度，所以我们传递指针A作为它的参数。

显然指向Ais not的指针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调用。

于 2012-10-22T16:47:02.790 回答
5

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

于 2012-10-22T16:54:41.607 回答
4

所有这些都来自这部分代码：

if(lchild <= rchild)
    return rchild + 1;
else
    return lchild + 1;

您将自己添加+1到树的叶子中获得的结果中。这些不断累加，直到您退出函数的所有递归调用并到达根节点。

于 2012-10-22T16:34:03.383 回答
2

请记住，在二叉树中，一个节点最多有 2 个子节点（左和右）

它是一种递归算法，所以它一遍又一遍地调用自己。

如果 temp（正在查看的节点）为 null，则返回 0，因为该节点什么都不是，不应该计算在内。这是基本情况。

如果正在查看的节点不为空，则它可能有子节点。所以它得到左子树的最大深度（并为当前节点的级别加 1）和右子树（为当前节点的级别加 1）。然后它比较两者并返回两者中的较大者。

它深入到两个子树（temp->left 和 temp->right）并重复操作，直到它到达没有子节点的节点。那时它将在左右调用 maxDepth，这将为 null 并返回 0，然后开始返回调用链。

因此，如果您有一个由三个节点组成的链（例如 root-left1-left2），它将下降到 left2 并调用 maxDepth(left) 和 maxDepth(right)。每个都返回 0（它们为空）。然后它又回到了left2。它比较，两者都是0，所以两者中的较大者当然是0。它返回0 + 1。然后我们在 left1 - 重复，发现 1 是它的左 n 右中的较大者（也许它们是相同的或者它没有右孩子）所以它返回 1+1。现在我们在根，同样的事情，它返回 2+1 = 3，这是深度。

于 2012-10-22T16:38:02.333 回答
2

因为深度是用前一个节点+1计算的

于 2012-10-22T16:34:14.937 回答
0

要找到二叉树的最大深度继续向左遍历树，基本上执行DFS
或者我们可以通过三种不同的递归方式找到二叉搜索树的深度

– using instance variables to record current depth and total depth at every level
– without using instance variables in top-bottom approach
– without using instance variables in bottom-up approach
于 2013-07-13T19:15:33.363 回答
0

我认为这是正确的答案

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return -1;
}
于 2019-07-04T05:59:33.237 回答
0

代码片段可以简化为：

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return 0;
}

查看此代码的一个好方法是自上而下：

如果 BST 没有节点会怎样？我们将拥有root = NULL并且该函数将立即返回预期的深度0。

现在假设树中填充了许多节点。从顶部开始，if条件将true针对根节点。然后我们通过将这些子树的根传递给 来询问左子树和右子树的最大深度是多少maxDepth。根的 LST 和 RST都比根深一级，所以我们必须加一才能得到传递给函数的树的深度。 root

于 2015-09-09T00:10:43.260 回答