問題定義

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

計算一個二叉樹的最大距離有兩個情況:

• 情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。

• 情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。

思路：

1，后序遍歷每一節點，找出該節點到最右邊的距離以及最左邊的距離；

2，找到之和最大的即可。

//需保存左子樹中最長距離、右子樹最長距離和當前樹的深度。

//以下提供兩種方法。

#include<iostream>
#include<stack>
using?namespace?std;
int?max(int?l,int?r)
{return?l>r?l:r;
}
struct?BinaryTreeNode
{int?data;BinaryTreeNode*?left;BinaryTreeNode*?right;BinaryTreeNode(int?x):data(x),?left(NULL),?right(NULL){}
};
class?BinaryTree
{
protected:BinaryTreeNode*?_root;BinaryTreeNode*?_CreateBinaryTree(int*?arr,?int&?index,?int?size){BinaryTreeNode*?root?=?NULL;if?(index?<?size&&arr[index]?!=?'#'){root?=?new?BinaryTreeNode(arr[index]);root->left?=?_CreateBinaryTree(arr,?++index,?size);root->right?=?_CreateBinaryTree(arr,?++index,?size);}return?root;}public:BinaryTree():_root(NULL){}BinaryTree(int?*arr,?int?size){int?index?=?0;_root?=?_CreateBinaryTree(arr,?index,?size);}/*int?MaxTwoNodeDistance(){if(_root==NULL){return?0;}int?maxDistance=0;_Distance(_root,maxDistance);return?maxDistance;}*/int?MaxTwoNodeDistance(){if(_root==NULL)return?0;int?maxLeft=0;int?maxRight=0;return?_Distance(_root,maxLeft,maxRight);}int?Height(){return?_Height(_root);}void?PreOrder_Non(){if?(_root?==?NULL)return;BinaryTreeNode*?cur?=?_root;stack<BinaryTreeNode*>?s;s.push(_root);while?(!s.empty()){cur?=?s.top();printf("%d?",?cur->data);s.pop();if?(cur->right)s.push(cur->right);if?(cur->left)s.push(cur->left);}cout?<<?endl;}
protected:int?_Distance(BinaryTreeNode*?root,int&?left,int?&right){if(root==NULL){left=0;right=0;return?0;}int?mll,mlr,mrl,mrr,dl,dr;if(root->left==NULL){left=0;dl=0;}else{dl=_Distance(root->left,mll,mlr);left=max(mll,mlr)+1;}if(root->right==NULL){right=0;dr=0;}else{dr=_Distance(root->right,mrl,mrr);right=max(mrl,mrr)+1;}return?max(max(dl,dr),left+right);}/*int?_Distance(BinaryTreeNode*?root,int&?max){if(root==NULL)return?0;int?maxLeft=0;int?maxRight=0;if(root->left){maxLeft=_Distance(root->left,max);if(maxLeft>max)max=maxLeft;}if(root->right){maxRight=_Distance(root->right,max);if(maxRight>max)max=maxRight;}if(maxLeft+maxRight>max)max=maxLeft+maxRight;return?maxLeft>maxRight?maxLeft+1:maxRight+1;	}*/int?_Height(BinaryTreeNode*?root){if?(root?==?NULL)return?0;int?left?=?_Height(root->left);int?right?=?_Height(root->right);return?left?>?right???left?+?1?:?right?+?1;}};
int?main()
{int?arr1[]={1,2,4,5,'#','#','#',7,'#','#',3,'#',6};int?arr2[]={1,2,3,4,'#','#','#',5,'#',6};BinaryTree?t1(arr1,sizeof(arr1)/sizeof(arr1[0]));t1.PreOrder_Non();cout<<t1.MaxTwoNodeDistance()<<endl;BinaryTree?t2(arr2,sizeof(arr2)/sizeof(arr2[0]));t2.PreOrder_Non();cout<<t2.MaxTwoNodeDistance()<<endl;
}