试图找到二叉树的深度

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

Answer 2

你离得很近，你不需要depthCurrent指针

findthedepth(root->rightp(), depthtotal /*, depthcurrent*/);
right = *depthtotal; // update the total depth captured in right
// *depthcurrent = 0; (no use)
findthedepth(root->leftp(), depthtotal /*, depthcurrent*/);
left = *depthtotal; // update the total depth captured in left