题目要求：

　　如果我们把二叉树看成一个图，父子结点之间的连线看成是双向的，我们姑且定义“距离”为两节点之间边的个数。写一个程序，求一颗二叉树中距离最远的两个结点之间的距离。

　　参考资料：编程之美3.8

题目分析：

　　最远距离要么经过根结点，要么不经过根结点在左子树中，要么不经过根结点在右子树中。根据这个思路加上递归就可以实现代码。

代码实现：

 

#include 
      
       using namespace std;typedef struct BinaryTree{    struct BinaryTree *left,*right;    int data;}BinaryTree;void initTree(BinaryTree **p);int maxDistance(BinaryTree *root);int main(void){    BinaryTree *root;    initTree(&root);    cout << "The max distance is " << maxDistance(root) << endl;    return 0;}int core(BinaryTree *root,int &depth);int max(int a,int b){    if(a>b)        return a;    else        return b;}int maxDistance(BinaryTree *root){    int depth;    return core(root,depth);}//depth为当前结点到叶子结点的最大长度//maxleft为当前结点的左子树中的最大距离//maxright为当前结点的右子树中的最大距离//因此最大距离要么是经过根结点的，则最大距离为ld+rd；要么是不经过根结点在左子树中//，则最大距离为maxleft;要么是不经过根结点在右子树中，则最大距离为maxright.int core(BinaryTree *root,int &depth){    if(root==NULL)    {        depth = 0;        return 0;    }    int ld,rd;    int maxleft = core(root->left,ld);    int maxright = core(root->right,rd);    depth = max(ld,rd)+1;    return max(maxleft,max(maxright,ld+rd));}//      10//     / \//    5   12//   / \//  4   7void initTree(BinaryTree **p){    *p = new BinaryTree;    (*p)->data = 10;     BinaryTree *tmpNode = new BinaryTree;    tmpNode->data = 5;    (*p)->left = tmpNode;     tmpNode = new BinaryTree;    tmpNode->data = 12;    (*p)->right = tmpNode;    tmpNode->left = NULL;    tmpNode->right = NULL;     BinaryTree *currentNode = (*p)->left;     tmpNode = new BinaryTree;    tmpNode->data = 4;    currentNode->left = tmpNode;    tmpNode->left = NULL;    tmpNode->right = NULL;     tmpNode = new BinaryTree;    tmpNode->data = 7;    currentNode->right = tmpNode;    tmpNode->left = NULL;    tmpNode->right = NULL; }