c++实现二叉树中节点的最大距离 - c++编程基础

文章前半部分能懂，可是后面的Milo不是很理解，可能有待以后学习.....

微软面试题之一，难度系数中，题目描述如下：

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

逻辑分析：

1、看到这道题的时候，很容易产生一种错觉，这题不就是求二叉树高度吗。。。显然，出题人不是小白，所以这里面一定有文章，继而注意到“双向”，玄机也正在此处。两张图说明一切，不解释。

2、题意清楚了，下一步就是分析如何去做，我们都知道，但凡是树的题目，一般都要考虑递归解。而针对这道题，我们通过分析可以得到几个比较显眼的结论：最长的路径一定包含叶子；最长的路径有两种情况，含有根节点，从左子树最深节点，到右子树最深节点，或者是不含根节点，而是左子树或者右子树的最长路径，递归而下，也就是上图的A，B。

3、总结上述说法，即是相距最远的两个节点，一定是两个叶子节点，或者一个叶子节点到根节点。对于任意一个节点，以该节点为根R，假设该节点有k个孩子节点，那么相距最远的两个节点U，V要么经过R（U、V也就是不同子树上的最深节点），要么不经过R，而是根的某一棵子树，且U、V一定也是子树的左右子树最深节点。

4、显然，我们自上而下的，采用类似深度遍历的方法递归下去，而又采用自底向上的动态规划思想，加以解决。

设第K棵子树中最远的两个节点Uk和Vk，其距离定义为d(Uk,Vk)，那么节点Uk或Vk即为子树K到根节点Rk距离最长的节点。不失一般性，我们设Uk为子树K中到根节点Rk距离最长的节点，其到根节点的距离定义为d(Uk,R)。取d(Ui,R)(1<=i<=k)中最大的两个值max1和max2，那么经过根节点R的最长路径为max1+max2+2，所以树R中相距最远的两个点的距离为：max{d(U1,V1),…, d(Uk,Vk),max1+max2+2}。而采用深度遍历的模型，我们知道，每一个节点都只遍历一次，且所有节点都需要经过遍历，那么时间复杂度为O(|E|)=O(|V|-1)，其中V为点的集合，E为边的集合。

下面给出编程之美上的代码

[cpp] view plaincopyprint

#include #include
struct NODE
{ NODE *pLeft;
NODE *pRight; int nMaxLeft;
int nMaxRight; char chValue;
};
int nMaxLen = 0;
void FindMaxLen(NODE* root) {
//递归结束 if(root==NULL) return;
//左树为空
if(root->pLeft==NULL) root->nMaxLeft=0;
//右树为空
if(root->pRight==NULL) root->pRight=0;
//左树不为空
if(root->pLeft!=NULL) {
FindMaxLen(root->pLeft); }
//右树不为空
if(root->pRight!=NULL) {
FindMaxLen(root->pRight); }
//求左子树最大距离
if(root->pLeft!=NULL) {
int nTempMax=0; if(root->pLeft->nMaxLeft>root->pLeft->nMaxRight)
nTempMax=root->pLeft->nMaxLeft; else
nTempMax=root->pLeft->nMaxRight; root->nMaxLeft=nTempMax+1;
}
//求右子树最大距离 if(root->pRight!=NULL)
{ int nTempMax=0;
if(root->pRight->nMaxLeft>root->pRight->nMaxRight) nTempMax=root->pRight->nMaxLeft;
else nTempMax=root->pRight->nMaxRight;
root->nMaxRight=nTempMax+1; }
//更新最大距离
if(root->nMaxLeft+root->nMaxRight>nMaxLen) nMaxLen=root->nMaxLeft+root->nMaxRight;
}
NODE* InitTree() {
NODE* tree[10];
for(int i=0;i<10;i++) {
tree[i]=(NODE*)malloc(sizeof(NODE)); tree[i]->nMaxLeft=0;
tree[i]->nMaxRight=0; tree[i]->pLeft=NULL;
tree[i]->pRight=NULL; tree[i]->chValue=(char)i;
} for(i=0;i<=2;i++)
{ tree[i]->pLeft=tree[2*i+1];
tree[i]->pRight=tree[2*i+2]; }
tree[3]->pLeft=tree[7]; tree[5]->pRight=tree[8];
return tree[0]; }
int main()
{ FindMaxLen(InitTree());
printf("%d\n",nMaxLen); return 0;

}

#include 
    
     
#include 
     
       struct NODE { NODE *pLeft; NODE *pRight; int nMaxLeft; int nMaxRight; char chValue; }; int nMaxLen = 0; void FindMaxLen(NODE* root) { //递归结束 if(root==NULL) return; //左树为空 if(root->pLeft==NULL) root->nMaxLeft=0; //右树为空 if(root->pRight==NULL) root->pRight=0; //左树不为空 if(root->pLeft!=NULL) { FindMaxLen(root->pLeft); } //右树不为空 if(root->pRight!=NULL) { FindMaxLen(root->pRight); } //求左子树最大距离 if(root->pLeft!=NULL) { int nTempMax=0; if(root->pLeft->nMaxLeft>root->pLeft->nMaxRight) nTempMax=root->pLeft->nMaxLeft; else nTempMax=root->pLeft->nMaxRight; root->nMaxLeft=nTempMax+1; } //求右子树最大距离 if(root->pRight!=NULL) { int nTempMax=0; if(root->pRight->nMaxLeft>root->pRight->nMaxRight) nTempMax=root->pRight->nMaxLeft; else nTempMax=root->pRight->nMaxRight; root->nMaxRight=nTempMax+1; } //更新最大距离 if(root->nMaxLeft+root->nMaxRight>nMaxLen) nMaxLen=root->nMaxLeft+root->nMaxRight; } NODE* InitTree() { NODE* tree[10]; for(int i=0;i<10;i++) { tree[i]=(NODE*)malloc(sizeof(NODE)); tree[i]->nMaxLeft=0; tree[i]->nMaxRight=0; tree[i]->pLeft=NULL; tree[i]->pRight=NULL; tree[i]->chValue=(char

c++实现二叉树中节点的最大距离(一)