题目描述:写一个程序求二叉树中相距最远的两个节点之间的距离。图3-11 A和B即为所求距离最远的两个节点。
我们先作图,看能否找到规律
我们可以看到,所求的两个节点可能经过二叉树的根结点,也可能不经过二叉树的根结点。每个节点维护左右子树最大距离(叶子到当前根节点的最大距离),左子树的最大距离:max1,右子树最大距离:max2,另设所求的二叉树两个节点的最大距离是nMaxLen。如果max1+max2>nMaxLen,需要更新nMaxLen=max1+max2,遍历完整棵二叉树,我们得到nMaxLen。
代码如下:
struct NODE
{
NODE *pLeft;
NODE *pRight;
int nMaxLeft;
int nMaxRight;
char data;
};
int nMaxLen=0;
void FindMaxLen(NODE *pRoot)
{
if(pRoot==NULL)
return;
if(pRoot->pLeft==NULL)
pRoot->nMaxLeft=0;
if(pRoot->pRight==NULL)
pRoot->nMaxRight=0;
if(pRoot->pLeft)//判定条件可省略,不影响结果,但明显不大好,因为我们对pRoot->pLeft==NULL情况已做了处理
FindMaxLen(pRoot->pLeft);
if(pRoot->pRight)
FindMaxLen(pRoot->pRight);
if(pRoot->pLeft!=NULL)//注意()一定要加上
pRoot->nMaxLeft=1+(pRoot->pLeft->nMaxLeft>pRoot->pLeft->nMaxRight?pRoot->pLeft->nMaxLeft:pRoot->pLeft->nMaxRight);
if(pRoot->pRight!=NULL)
pRoot->nMaxRight=1+(pRoot->pRight->nMaxLeft>pRoot->pRight->nMaxRight?pRoot->pRight->nMaxLeft:pRoot->pRight->nMaxRight);
//更新nMaxLen
if(nMaxLen<pRoot->nMaxLeft+pRoot->nMaxRight)
nMaxLen=pRoot->nMaxLeft+pRoot->nMaxRight;
}