算法5(求二叉树中节点的最大距离)

题目：求二叉树中节点的最大距离.
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。
写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。

题目来源于：http://topic.csdn.net/u/20101011/16/2befbfd9-f3e4-41c5-bb31-814e9615832e.html

思路一：

题目要求一颗二叉树中两个节点之间的最大距离，由于父子节点之间边是双向的，所以这道题转换为求左子树的最大深度 + 右子树的最大深度就是二叉树中节点的最大距离。

例如：以下一颗树：

5

/ /

4 8

/ /

7 12

/

10

那么它的最大距离为4，即：4-->5-->8-->12-->10.其中"-->"的个数就是最大的距离数4.

代码如下：

/*--------------------------------
求二叉树的最大距离算法.
Copyright by yuucyf. 2011.05.06
----------------------------------*/

#include "stdafx.h"
#include <assert.h>
#include <iostream>
using namespace std;

typedef struct tagBSTNode
{
int nValue;
tagBSTNode *psLeft;
tagBSTNode *psRight;

tagBSTNode()
{
nValue = 0;
psLeft = psRight = NULL;
}
}S_BSTNode;

void DeleteAllNode(S_BSTNode* pRoot)
{
if (NULL == pRoot) return;

DeleteAllNode(pRoot->psLeft);
DeleteAllNode(pRoot->psRight);

delete pRoot;
}

void AddBSTreeNode(S_BSTNode* &pRoot, int nValue)
{
if (NULL == pRoot)
{
pRoot = new S_BSTNode;
assert(NULL != pRoot);
pRoot->nValue = nValue;
return;
}

if (pRoot->nValue > nValue)
{
AddBSTreeNode(pRoot->psLeft, nValue);
}
else if ( pRoot->nValue < nValue)
{
AddBSTreeNode(pRoot->psRight, nValue);
}
}


int GetMaxDepth(const S_BSTNode* pRoot)
{
if (NULL == pRoot) return 0;

if (NULL == pRoot->psLeft && NULL == pRoot->psRight)
{
return 0;
}

int nLeftDepth = 0, nRightDepth = 0;
if (NULL != pRoot->psLeft)
{
nLeftDepth = GetMaxDepth(pRoot->psLeft) + 1;
}

if (NULL != pRoot->psRight)
{
nRightDepth = GetMaxDepth(pRoot->psRight) + 1;
}

if (nRightDepth >= nLeftDepth)
{
return nRightDepth;
}
else
{
return nLeftDepth;
}
}

int GetMaxDistance(const S_BSTNode* pRoot)
{
if (NULL == pRoot) return 0;

int nLeftDepth = GetMaxDepth(pRoot->psLeft);
nLeftDepth += ((pRoot->psLeft != NULL) ? 1 : 0);

int nRightDepth =GetMaxDepth(pRoot->psRight);
nRightDepth += ((pRoot->psRight != NULL) ? 1 : 0);

return nLeftDepth + nRightDepth;
}


int _tmain(int argc, _TCHAR* argv[])
{
S_BSTNode *pRoot = NULL;
AddBSTreeNode(pRoot, 5);
AddBSTreeNode(pRoot, 4);
AddBSTreeNode(pRoot, 8);
AddBSTreeNode(pRoot, 7);
AddBSTreeNode(pRoot, 12);
AddBSTreeNode(pRoot, 10);

int nMaxDis = GetMaxDistance(pRoot);
cout << "Max distance is " << nMaxDis << endl;
DeleteAllNode(pRoot);

return 0;
}

思路二：

其实想法跟思路一是类似的，具体实现看以下代码，不过你会发现下面的实现没有比思路一中的实现更为容易理解。