問題定義
如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。寫一個程序求一棵二叉樹中相距最遠的兩個節點之間的距離。
計算一個二叉樹的最大距離有兩個情況:
情況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;
}
