【问题描述】
从二叉树的节点 A 出发，可以向上或者向下走，但沿途的节点只能经过一次，
当到达节点 B 时，路径上的节点数叫作 A 到 B 的距离。
现在给出一棵二叉树，求整棵树上每对节点之间的最大距离。
【输入形式】
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。
（如果 lch 为 0 则表示 fa 没有左儿子，如果 rch 为 0 则表示 fa 没有右儿子）
【输出形式】
输出一个整数表示答案。
【样例输入】
5 1
1 2 3
2 0 5
3 0 7
5 0 0
7 0 0
【样例输出】
5
【样例说明】
1
/ \
2 3
\ \
5 7 从 5 到 7 经历 5 个节点。
思路
分两步：
1.根据输入建立二叉树
2.求最大距离
建立一个node结构体，增加flag:1表示根，2表示中间，3表示叶子
在建立的时候是只能对于根和叶子操作的
中间包括了已经确定了下面2个空节点，或者下面一个儿子的
伪代码：
node**p 用于存放已经出现过的节点
for(i<n){
在p中找父亲节点，找到的话返回p中的标号，如果father出现过，它必为叶节点
if(标号！=-1){
父节点的flag从3变成2;//表示从叶子变成中间不能操作的
}
else {
node[tail++]=new node(father);
}
在p中找左右儿子节点，找到的话返回p中的标号，如果儿子出现过，它必为根节点
if(标号！=-1){
儿子节点的flag从1变成2;//表示从叶子变成中间不能操作的
}
else new 节点 flag=2;
设置父子关系
}
根据根节点的值寻找它在p中的位置
//求最大距离，分包裹函数和递归函数，在height递归函数中求出最大距离
//对于每一个节点，最大距离=max(最大高度,左子树的最大距离，右子树的最大距离）
#include <iostream>
using namespace std;
struct node
{
int data = -1;
int flag = 0; //根：1 中：2 叶：3
node* left = NULL;
node* right = NULL;
node* father = NULL;
node() {};
node(char item=-1, int Flag=0,node* L = NULL, node* R = NULL, node* f = NULL) :data(item),flag(Flag),left(L), right(R), father(f) {};
~node() {};
};
class bintree
{
private:
node** exist = NULL;
node* root = NULL;
int tail=0;
bintree(int x) { root = new node(x); }
void preOrder(node *t)const{
if (t!=NULL) {
cout<<t->data;
preOrder(t->left);
preOrder(t->right);
}
}
int height(node*t,int & dis){
if (t==NULL) return 0;
else{
int hl=0,hr=0;
hl=height(t->left,dis);
hr=height(t->right,dis);
dis=max(hl+hr+1,dis);
return max(hl,hr)+1;
}
}
public:
bintree() {};
int distance(){
int dis=0;
height(root,dis);
return dis;
}
void preOrder()const{
if(root!=NULL){
cout<<"\n先序遍历：";//\n加在”“里面也可以换行
preOrder(root);
}
}
int find_it(int target,node**exist){
if (tail==0) return -1;
for (int cur=0; cur<tail; cur++){
if (target==exist[cur]->data){
return cur;
}//已存在的节点中找到父亲了
}
return -1;
}
void create()//生成一个正整数树,使用三叉链表
{
int num=0,root_data=0;
//cur用于数组的迭代搜寻，tail是exist数组尾部
cin >> num >> root_data;
node** exist = new node * [num + 1]; //exist 记录已有节点
for (int i=0; i<num; i++) {
int fa=0,l=0,r=0,fptr=0,lptr=0,rptr=0;
cin>>fa>>l>>r;
fptr=find_it(fa,exist);
if (fptr!=-1) //在已有节点中找到了父亲
exist[fptr]->flag=2;
else {
exist[tail]=new node(fa);// node*f=new node(fa); exist[tail++]=f?
exist[tail]->flag=1;
fptr=tail;
tail++;
}
if (l!=0) {
lptr=find_it(l,exist);
if (lptr!=-1) exist[lptr]->flag=2;
else {
exist[tail]=new node(l);
lptr=tail;
tail++;
}
exist[lptr]->father=exist[fptr];
exist[fptr]->left=exist[lptr];
}
if (r!=0) {
rptr=find_it(r,exist);
if (rptr!=-1) exist[rptr]->flag=2;
else {
exist[tail]=new node(r);
rptr=tail;
tail++;
}
exist[rptr]->father=exist[fptr];
exist[fptr]->right=exist[rptr];
}
}
int root_ptr=find_it(root_data, exist);
root=exist[root_ptr];
delete[]exist;
}
~bintree() { clear(); }
void clear()
{
clear(root);
}
void clear(node*& t)
{
if (t == NULL) return;
clear(t->left);
clear(t->right);
delete t;
t = NULL;
}
};
int main()
{
bintree mytree;
mytree.create();
cout<<mytree.distance();
return 0;
}
启发
1.一开始用两个数组leave root去记录是根还是树叶，但是就很麻烦，如果就用一个数组去记录，但是一个结构体里面有一个flag 标记就方便很多
2.Node**p 就是指针数组，和Nodep[]是一样的
3.犯了一个很常见的错误。
Nodep=root->next;
p=new node
指针变掉了
正确：root->next=new node
但是，在cg编译的时候还是4和5数据点每过，显示的是编译错误，找不到错误呜呜，还是等数据点处来看看吧，此处贴上别的大佬的解答。
#define NULL 0
#include <iostream>
using namespace std;
struct node
{
int data = -1;
node* left = NULL;
node* right = NULL;
node* father = NULL;
int layer = 0;
node() {};
node(char item, node* L = NULL, node* R = NULL, node* f = NULL, int lay = 0) :data(item), left(L), right(R), father(f), layer(lay) {};
~node() {};
};
class bintree
{
node** leaves = NULL;
int leafnum = -1;
node* root = NULL;
public:
bintree() {};
bintree(int x) { root = new node(x); }
void create()//生成一个正整数树,使用三叉链表，同时记录每个结点的层数
{
int cur = 0, top = 0, read, l, r, n, num;
cin >> num >> read;
leaves = new node * [num + 1];
node** p = new node * [num + 1]; //p 记录已有节点
int* d = new int[num + 1]; //d是已经有的节点的数据
for (int i = 0; i <= num; ++i)
{
p[i] = NULL;
d[i] = -1;
}
p[0] = root = new node(read);
d[0] = read;
root->layer = 1;
for (int i = 0; i < num; ++i)
{
cin >> n >> l >> r;
for (int j = top; j >= 0; --j)
{
if (n == d[j]) //如果父亲已经出现过了
{
cur = j; //cur记录父亲的标号
break;
}
}
if (l != 0)
{
p[cur]->left = new node(l);
++top;
p[top] = p[cur]->left;
d[top] = l;
p[top]->father = p[cur];
p[top]->layer = (p[cur]->layer) + 1;
}
if (r != 0)
{
p[cur]->right = new node(r);
++top;
p[top] = p[cur]->right;
d[top] = r;
p[top]->father = p[cur];
p[top]->layer = (p[cur]->layer) + 1;
}
if (l == 0 && r == 0)//无左右儿子，为叶子
{
++leafnum;
leaves[leafnum] = p[cur];
}
}
delete[]p;
}
~bintree() { clear(); }
void clear()
{
clear(root);
delete[]leaves;
}
void clear(node*& t)
{
if (t == NULL) return;
clear(t->left);
clear(t->right);
delete t;
t = NULL;
}
int findlongest()
{
int maxdistance = 0;
int sharenodelayer = 0;
node* far = NULL;
int maxlayer = 1;
if (leafnum == 0) return maxlayer;
for (int i = 0; i <= leafnum; ++i)
{
if (leaves[i]->layer > maxlayer)
{
far = leaves[i];
maxlayer = far->layer;
}
}
for (int i = 0; i <= leafnum; ++i)
{
if (leaves[i] == far) continue;
node* curleaf = leaves[i];
int curlayer = curleaf->layer;
node* maxcurnode = far;
for (int j = 0; j < maxlayer - curlayer; ++j)//较长的一条链向上追溯到与比对的链同样长度的层次
{
maxcurnode = maxcurnode->father;
}
for (int j = curlayer; j > 0; --j)//两条链同时向上追溯，查找是否有共同的祖先
{
if (curleaf == maxcurnode)
{
sharenodelayer = j;
break;
}
else
{
curleaf = curleaf->father;
maxcurnode = maxcurnode->father;
}
}
if (curlayer + maxlayer - 2 * sharenodelayer > maxdistance) maxdistance = curlayer + maxlayer - 2 * sharenodelayer;
}
if (maxdistance < maxlayer) maxdistance = maxlayer - 1;
return maxdistance + 1;
}
};
int main()
{
bintree mytree;
mytree.create();
cout << mytree.findlongest();
return 0;
}
另一个大佬写的建立树的过程
转载：https://blog.csdn.net/echo_xiao9/article/details/105796434
查看评论