看到这题，{dy}时间就联想到了求二叉树深度（通过分别求左右子树的深度，然后合并（取{zd0}值加1）从而得到了根节点的深度（其实就是分治思想））
代码如下：
int Depth(Node *p)
{
int l_d , r_d;
if(p == NULL)
{
return 0;
}
l_d = Depth(p->lChild);
r_d = Depth(p->rChild);
return Max(l_d , r_d) + 1;
}
而现在我们要求节点的{zd0}距离，我们可以用同样的方法去思考：对一个节点A，其子树中节点的{zd0}距离一定是A左子树的深度 + A右子树的深度，所以我们只要用“分治”的思想递归求解即可，并且用一个MaxLen来维护{zd0}值：
int MaxLen = 0;
int FindMaxLen(Node *p)
{
int l_Len , r_Len;
if(p == NULL)
{
return 0;
}
l_Len = FindMaxLen(p->lChild);
r_Len = FindMaxLen(p->rChild);
MaxLen = Max(l_Len + r_Len , MaxLen);
return Max(l_Len , r_Len) + 1;
}
个人感觉比书上的简洁很多~
posted on 2010-06-22 13:11 阅读(3) 所属分类:
