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;
    }
}

标签： c++binary-tree

Answer 1

有两种情况需要考虑：

• 一棵空树的深度为零；
• 一棵非空树比它的两个子树的深度多一层，所以它有 depth 1 + max(depth_left, depth_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);
}