[程式設計之美-05]求二叉樹中節點的最大距離

題目:如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義”距離”為兩節點之間邊的個數。寫一個程式，求一棵二叉樹中相距最遠的兩個節點之間的距離.

例如:

10

/ \

5 12

/ \

4 7

這棵樹的話,最大距離為3.分别路徑為4,5,10,12共3條邊,7,5,10,12共3條邊,是以最大距離為3.

遞歸的思想,分别考慮左右子樹的,從根節點開始.

代碼如下:

#include<iostream>
using namespace std;

struct BiTreeNode
{
    int m_nValue;
    BiTreeNode *m_pleft;
    BiTreeNode *m_pright;
    int m_nMaxLeft;
    int m_nMaxRight;
};

int nMaxLen = ;

void findMaxLen(BiTreeNode *pRoot);

void addBiTreeNode(BiTreeNode *&pCurrent, int value);


int main()
{
    BiTreeNode *pRoot = NULL;
    addBiTreeNode(pRoot, );
    addBiTreeNode(pRoot, );
    addBiTreeNode(pRoot, );
    addBiTreeNode(pRoot, );
    addBiTreeNode(pRoot, );

    findMaxLen(pRoot);
    cout<<nMaxLen<<endl;
    return ;
}



void findMaxLen(BiTreeNode *pRoot)
{
    if(pRoot == NULL)
        return ;

    if(pRoot->m_pleft == NULL)
        pRoot->m_nMaxLeft = ;

    if(pRoot->m_pright == NULL)
        pRoot->m_nMaxRight = ;

    if(pRoot->m_pleft != NULL)
        findMaxLen(pRoot->m_pleft);

    if(pRoot->m_pright != NULL)
        findMaxLen(pRoot->m_pright);

    if(pRoot->m_pleft != NULL)
    {
        int nTempMax = ;

        if(pRoot->m_pleft->m_nMaxLeft > pRoot->m_pleft->m_nMaxRight)
            nTempMax = pRoot->m_pleft->m_nMaxLeft;
        else
            nTempMax = pRoot->m_pleft->m_nMaxRight;

        pRoot->m_nMaxLeft = nTempMax + ;
    }

    if(pRoot->m_pright != NULL)
    {
        int nTempMax = ;

        if(pRoot->m_pright->m_nMaxLeft > pRoot->m_pright->m_nMaxRight)
            nTempMax = pRoot->m_pright->m_nMaxLeft;
        else
            nTempMax = pRoot->m_pright->m_nMaxRight;

        pRoot->m_nMaxRight = nTempMax + ;
    }

    if(pRoot->m_nMaxLeft + pRoot->m_nMaxRight > nMaxLen)
        nMaxLen = pRoot->m_nMaxLeft + pRoot->m_nMaxRight;   
}



void addBiTreeNode(BiTreeNode *&pCurrent, int value)
{
    if(pCurrent == NULL)
    {
        BiTreeNode *pBiTree = new BiTreeNode();
        pBiTree->m_nValue = value;
        pBiTree->m_pleft = NULL;
        pBiTree->m_pright = NULL;
        pCurrent = pBiTree;
    }
    else
    {
        if((pCurrent->m_nValue) > value)
            addBiTreeNode(pCurrent->m_pleft, value);
        else if((pCurrent->m_nValue) < value)
            addBiTreeNode(pCurrent->m_pright, value);   
    }
}