T9-2 求二叉树中节点间的宽度

lijunjie03 / 2023-05-13 / 原文

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

深度：4 宽度：4（同一层最多结点个数）

结点间距离： ⑧→⑥为8 (3×2+2=8)

⑥→⑦为3 （1×2+1=3）

注：结点间距离的定义：由结点向根方向（上行方向）时的边数×2，

与由根向叶结点方向（下行方向）时的边数之和。

输入格式

输入文件第一行为一个整数n(1≤n≤100)，表示二叉树结点个数。接下来的n-1行，表示从结点x到结点y（约定根结点为1），最后一行两个整数u、v，表示求从结点u到结点v的距离。

输出格式

三个数，每个数占一行，依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

输入输出样例

输入 #1

输出 #1

4
4
8

#include <iostream>
#include <algorithm>
using namespace std;//91，需要深搜完善（5/10 已ac）
struct node{
    int father;  //爸爸
    int left;    //左儿子
    int right;   //右儿子
    int deep;    //深度
    int data;    //记录节点走过没
}a[10001];
int sum[101];
int n,x,y,s,t,maxx=1;
int lca(int x,int y){      //莽夫版lca（能看得懂版）
    a[x].data=1;           //把x的节点记录已走过
    while(a[x].father!=0){ //遍历至根节点
        x=a[x].father;     //更新遍历爸爸
        a[x].data=1;       //记录已走过
    }
    while(a[y].data!=1){   //遍历至x节点已走过的节点，找到最近公共祖先
        y=a[y].father;
    }
    return y;
}
void dfs(int id,int deep)
{
    if(!id) return;
    a[id].deep=deep;
    maxx=max(maxx,deep);
    dfs(a[id].left,deep+1);
    dfs(a[id].right,deep+1);
}
int main(){

    cin>>n;
    //初始化
    a[1].deep=1;    //根节点的深度为1
    a[1].father=0;  //根节点没有爸爸
    //建树
    for(int i=1;i<n;i++){
        cin>>x>>y;
        if(a[x].left==0)    //这个节点是否有左儿子
            a[x].left=y;     //变成左儿子
        else                //变成右儿子
            a[x].right=y;
        a[y].father=x;
        /*a[y].deep=a[x].deep+1;   //更新深度
        //求深度
        if(a[y].deep>maxx)       //求出最大深度，第一个问题完成
            maxx=a[y].deep;*/
    }
    dfs(1,1);//求深度，与最大深度
    cin>>s>>t;
    int f=lca(s,t),num=0,num1=0;//求最近公共祖先
    while(s!=f){                //记录s到最近公共祖先有多少条边
        s=a[s].father;
        num++;
    }
    num*=2;   //结点间距离的定义：由结点向根方向（上行方向）时的边数×2，
    while(t!=f){               //记录t到最近公共祖先有多少条边
        t=a[t].father;
        num1++;
    }
    //求宽度
    for(int i=1;i<=n;i++)      //把每一个深度有多少个节点记录
        sum[a[i].deep]++;
    sort(sum+1,sum+1+100);
    cout<<maxx<<endl<<sum[100]<<endl<<num+num1; //sum[100]是最大的宽度节点个数

    return 0;
}