c++ - 尝试找到二叉树的深度

Question

我正在尝试写一些东西来确定二叉树的最大深度，但到目前为止只得到了一个不断返回树中节点数量的东西，而下面的另一个东西总是一个又一个或更少。经过几个小时的尝试调整后，我真的需要一些建议..

void findthedepth(nodeoftree<node>* root, int* depthtotal, int* depthcurrent){

    int left = 0, right = 0;

    if( root == nullptr ){
        *depthtotal = 0;
        *depthcurrent = 0;
        return;
    }

    findthedepth(root->rightp(), depthtotal, depthcurrent);
    right = *depthcurrent;

    *depthcurrent = 0;

    findthedepth(root->leftp(), depthtotal, depthcurrent);
    left = *depthcurrent;


    if (left > right){ 
        *depthtotal += left + 1;
    }
    else { 
        *depthtotal += right + 1;
    }
}

Answer 1

有两种情况需要考虑:

• 空树的深度为零；
• 非空树的层数比其两个子树的深度多一级，因此它的深度 1 + max(depth_left, height_right)。

如果我们用 C++ 写出:

int depth(nodeoftree<node>* root) {
    if (root == nullptr)
        return 0;

    int depth_left = depth(node->leftp());
    int depth_right = depth(node->rightp());
    return 1 + max(depth_left, depth_right);
}