求二叉树中节点间的最大距离（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####,会建立一颗如下的二叉树：