DS binary tree - maximum distance of binary tree nodes

Title Description

The distance between two nodes of a binary tree is that one node passes through the parent node , The number of branches that an intermediate node such as an ancestor node passes through to reach another node . The maximum distance of a binary tree node is the maximum distance between all nodes . for example , The maximum distance between nodes of the binary tree shown in the figure below is 3,C and D Distance of .

A binary tree is created in a preordered traversal order ,# Empty tree . Calculate the two nodes of the maximum distance and the maximum distance of the binary tree node ( Suppose that the two nodes with the largest distance in the binary tree are unique ）.

 

Input

Number of tests T

The first 2 After that T That's ok , Each line traverses the result of a binary tree first （# Empty tree ）

Output

For every binary tree , The maximum distance between the nodes of the output tree and the nodes with the maximum distance , See the example for the output format .

  The sample input

3
A##
ABC##EF#G###D##
ABEH###F#K###

Sample output

0:
5:G D
4:H K

Code

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+20;
struct NODE{
    char data;
    int d,d2;
    NODE *l,*r,*fa;
    NODE(){
        l=NULL;
        r=NULL;
        fa=NULL;
        d=0;
    }
};
int t,n;
string s;
int maxx;
NODE *qwe=new NODE;
NODE *node=new NODE;

int id=0;
void build(NODE *&head,NODE *fa){
    if(id>=n || s[id]=='#'){
        head=NULL;
        id++;
        return ;
    }
    head=new NODE;
    head->data=s[id];
    head->fa=fa;
    head->d=fa->d+1;
    if(head->d>maxx){
        maxx=head->d;
        qwe=head;
    }
    id++;
    build(head->l,head);
    build(head->r,head);
}

bool check(NODE *a,NODE *b){
    queue<NODE *> qq;
    if(a->l) qq.push(a->l);
    while(!qq.empty()){
        auto now=qq.front();
        qq.pop();
        if(now->data==b->data) return false;
        if(now->l) qq.push(now->l);
        if(now->r) qq.push(now->r);
    }
    return true;
}

void find(NODE *head){
    queue<NODE*> q;
    map<char,int> mp;
    q.push(qwe);
    mp[qwe->data]++;
    qwe->d2=0;
    int ans=0;
    NODE *asd=new NODE;
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        if(now->d2>ans){
            ans=now->d2;
            asd=now;
        }
        if(now->fa!=node && now->fa!=NULL && mp.count(now->fa->data)==0){
            now->fa->d2=now->d2+1;
            q.push(now->fa);
            mp[now->fa->data]++;
        }
        if(now->l!=node &&now->l && mp.count(now->l->data)==0){
            now->l->d2=now->d2+1;
            q.push(now->l);
            mp[now->l->data]++;
        }
        if(now->r!=node &&now->r && mp.count(now->r->data)==0){
            now->r->d2=now->d2+1;
            q.push(now->r);
            mp[now->r->data]++;
        }
    }
    cout<<ans<<":";
    if(ans!=0){
        if(head->l==NULL)
            cout<<asd->data<<" "<<qwe->data;
        else cout<<qwe->data<<" "<<asd->data;
    }
    cout<<endl;
}

int main(){
//    freopen("123.in","r",stdin);
    cin>>t;
    while(t--){
        cin>>s;
        n=s.length();
        id=0;
        NODE *head;
        maxx=0;
        build(head,node);
        find(head);
//        cout<<maxx<<" "<<qwe->data<<endl;
    }
    return 0;
}