2012.2-求最大叶子间距

实际上是一个求树的直径问题

#include <iostream>
using namespace std;
struct NODE
{
    NODE *pLeft;
    NODE *pRight;
};
 
struct RESULT
{
    int nMaxDistance;
    int nMaxDepth;
};
 
RESULT GetMaximumDistance(NODE* root)
{
    if (!root)
    {
        RESULT empty = { 0, -1 };   // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero.
        return empty;
    }
 
    RESULT lhs = GetMaximumDistance(root->pLeft);
    RESULT rhs = GetMaximumDistance(root->pRight);
 
    RESULT result;
    result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1);
    result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2);
    return result;
}
           

 代码经过改进之后

//改进的版本
int HeightOfBinaryTree(BinaryTreeNode*pNode, int&nMaxDistance){
	if (pNode == NULL)
		return -1;   //空节点的高度为-1
	//递归
	int nHeightOfLeftTree = HeightOfBinaryTree(pNode->m_pLeft, nMaxDistance) + 1;   //左子树的的高度加1
	int nHeightOfRightTree = HeightOfBinaryTree(pNode->m_pRight, nMaxDistance) + 1;   //右子树的高度加1
	int nDistance = nHeightOfLeftTree + nHeightOfRightTree;    //距离等于左子树的高度加上右子树的高度+2
	nMaxDistance = nMaxDistance > nDistance ? nMaxDistance : nDistance;            //得到距离的最大值
	return nHeightOfLeftTree > nHeightOfRightTree ? nHeightOfLeftTree : nHeightOfRightTree;
}
           

计算图的直径

int d[10][10];  // adjacency matrix
int ecc[10];    // 各點的偏心距
 
void diameter_radius()
{
    // Floyd-Warshall Algorithm
    for (int k=0; k<10; ++k)
        for (int i=0; i<10; ++i)
            for (int j=0; j<10; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
 
    // 計算偏心距
    memset(ecc, 0x7f, sizeof(ecc));
    for (int i=0; i<10; ++i)
        for (int j=0; j<10; ++j)
            ecc[i] = min(ecc[i], d[i][j]);
 
    // 計算直徑和半徑
    int diameter = 0;
    int radius = 1e9;
    for (int i=0; i<10; ++i)
    {
        diameter = max(diameter, ecc[i]);
        radius   = min(radius  , ecc[i]);
    }
 
/*
    // 直徑也可以這樣算
    for (int i=0; i<10; ++i)
        for (int j=0; j<10; ++j)
            diameter = max(diameter, d[i][j]);
*/
           

https://blog.csdn.net/zhanxufeng/article/details/80715185

https://blog.csdn.net/sunmenggmail/article/details/7739419

https://blog.csdn.net/forever_dreams/article/details/81051578 两次bfs + dfs