求二叉樹中節點間的最大距離（c++代碼完整實作）

//求一個二叉樹中節點間的最大距離，
//兩個節點的距離定義是這兩個節點間的邊的個數
//比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間複雜度 
#include <cstdlib>
#include <iostream>

#define OVERFLOW -2
using namespace std;
// 資料結構定義
struct NODE
{
     NODE* pLeft;        	// 左子樹
     NODE* pRight;      	// 右子樹
     int nMaxLeft;      	// 左子樹中的最長距離
     int nMaxRight;     	// 右子樹中的最長距離
     char chValue;    	// 該節點的值
};

int nMaxLen = 0;

// 尋找樹中最長的兩段距離
void FindMaxLen(NODE* pRoot)
{
     // 周遊到葉子節點，傳回
     if(pRoot == NULL)
     {
          return;
     }

     // 如果左子樹為空，那麼該節點的左邊最長距離為0
     if(pRoot -> pLeft == NULL)
     {
          pRoot -> nMaxLeft = 0; 
     }

     // 如果右子樹為空，那麼該節點的右邊最長距離為0
     if(pRoot -> pRight == NULL)
     {
          pRoot -> nMaxRight = 0;
     }

     // 如果左子樹不為空，遞歸尋找左子樹最長距離
     if(pRoot -> pLeft != NULL)
     {
          FindMaxLen(pRoot -> pLeft);
     }

     // 如果右子樹不為空，遞歸尋找右子樹最長距離
     if(pRoot -> pRight != NULL)
     {
          FindMaxLen(pRoot -> pRight);
     }

     // 計算左子樹最長節點距離
     if(pRoot -> pLeft != NULL)
     {
          int nTempMax = 0;
          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
          {
               nTempMax = pRoot -> pLeft -> nMaxLeft;
          }
          else
          {
               nTempMax = pRoot -> pLeft -> nMaxRight;
          }
          pRoot -> nMaxLeft = nTempMax + 1;
     }

     // 計算右子樹最長節點距離
     if(pRoot -> pRight != NULL)
     {
          int nTempMax = 0;
          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
          {
               nTempMax = pRoot -> pRight -> nMaxLeft;
          }
          else
          {
               nTempMax = pRoot -> pRight -> nMaxRight;
          }
          pRoot -> nMaxRight = nTempMax + 1;
     }

     // 更新最長距離
     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
     {
          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
     }
}
bool CreateBiTree(NODE ** pTree){
     char ch;
     cin>>ch;
     if(ch =='#') *pTree=NULL;
     else{
          if(!((*pTree)=(NODE*)malloc(sizeof(NODE))))
                    exit(OVERFLOW);
          (*pTree)->nMaxLeft=0;
          (*pTree)->nMaxRight=0;
          (*pTree)->chValue=ch;
          CreateBiTree(&(*pTree)->pLeft);
          CreateBiTree(&(*pTree)->pRight);     
     }
     return true;
     
}
int main(int argc, char *argv[])
{
    NODE *pRoot=NULL;
    bool flag=CreateBiTree(&pRoot);
    FindMaxLen(pRoot);
    cout<<nMaxLen<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}
           

編譯後運作該程式，按照先序周遊的順序建立二叉樹，比如輸入：abc##dg####,會建立一顆如下的二叉樹：