后序遍历基础上求二叉树的深度

Question

请问这样能准确计算二叉树的深度吗（deep初始调用时传入1，max默认为1）
根节点为空时特殊处理

int max=1;
//递归先序遍历
void RecurPreVisit(BTNode *p,int deep)
{
    if(p==NULL) return;


    RecurPreVisit(p->lchild,deep+1);
    RecurPreVisit(p->rchild,deep+1);

    //操作
    //-----------------------------------------
    //printf("%d ",p->data);

    if(deep>max) max=deep;


    //-----------------------------------------
}

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码片段中，您正在尝试通过后序遍历来计算二叉树的深度。然而，这段代码实际上是实现了一个先序遍历而不是后序遍历。为了根据后序遍历计算二叉树的深度，我们需要调整遍历顺序，确保左子树、右子树以及根节点的访问顺序正确。

以下是修正后的后序遍历函数，用于计算二叉树的深度：

int max = 1; // 初始化最大深度为1，因为至少有一个根节点

// 后序遍历
void RecurPostVisit(BTNode* p, int& deep)
{
    if (p == NULL) return;

    // 先遍历左右子树
    RecurPostVisit(p->lchild, deep);
    RecurPostVisit(p->rchild, deep);

    // 当前节点处理完之后更新深度
    if (deep < 1 + max) // 使用<而非>
        max = deep + 1;
}

// 主函数，从根节点开始调用
void CalculateTreeDepth(BTNode* root)
{
    RecurPostVisit(root, max);
    printf("The depth of the tree is: %d\n", max);
}

在这个版本中，我们首先遍历左子树，然后遍历右子树，最后处理根节点。这样可以确保我们总是对最远的叶子节点进行深度检查。注意，我们在RecurPostVisit函数中使用了引用传递deep参数，以便在递归过程中修改它。同时，在判断新深度是否更大的条件语句中，使用了<而非>，因为我们需要找到最小的深度值来表示整个树的最大深度。最后，在主函数CalculateTreeDepth中，调用RecurPostVisit并输出结果。