2020-07-07 二叉树深度

https://www.luogu.com.cn/problem/P4913

//set的使用
#include <iostream>
#include <cstdio>
#define MAXN 1000005
#define ll long long
#define inf 0x7fffffff
using namespace std;

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

int tree[MAXN];
int flag[MAXN];
int c[MAXN];
int C = 0;
int dfs(int x){
    C++;
    if (tree[x]==0) {
        flag[x] = max(C,flag[x]);
        return flag[x];
    }
    flag[x] = dfs(tree[x]);
    return flag[x];
}

int main(){
    int n = read();
    c[0] = 1;
    c[1] = 1;
    for(int i = 1; i<=n; i++){
        int a = read(),b = read();
        if(tree[i]!=0||i==1){
            int f = c[i];
            //printf("c[%d] = %d\n",tree[i],f);
            f+=1;
            c[a] = f;
            c[b] = f;
        }
        tree[a] = i;
        tree[b] = i;

    }
    int count = 0;
    for(int i = n; i>=1; i--){
         if (c[i]>count&&tree[i]!=0) {
            count = c[i];
        }
    }
    printf("%d",count);
    return 0;
}
/*
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
*/

超时解：

//set的使用
#include <iostream>
#include <cstdio>
#define MAXN 1000005
#define ll long long
#define inf 0x7fffffff
using namespace std;

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

int tree[MAXN];
int flag[MAXN];
int C = 0;
int dfs(int x){
    C++;
    if (tree[x]==0) {
        flag[x] = max(C,flag[x]);
        return flag[x];
    }
    flag[x] = dfs(tree[x]);
    return flag[x];
}

int main(){
    int n = read();
    for(int i = 1; i<=n; i++){
        int a = read(),b = read();
        tree[a] = i;
        tree[b] = i;
        flag[i] = -1;
    }
    int count = 0;
    for(int i = n; i>=1; i--){
        C = 0;
        if(tree[i]!=0) {
            dfs(i);
            //count = max(count,dfs(i));
        }
    }
    printf("%d",flag[1]);
    return 0;
}
/*
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
*/

AC解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

struct node{
    int l,r;
}a[1001000];//记录每个节点的左右节点

int Max = -1, n;

void dfs(int root,int step){
    if(root==0)
        return;//如果该节点为0（即上它的爸爸没有这个儿子），返回
    Max = max(Max,step);//记录最大值
    dfs(a[root].l,step+1);//搜索它的左儿子
    dfs(a[root].r,step+1);//搜索它的右儿子
    
}

int main(){
    cin>>n;//输入n
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;//输入该节点的左节点和右节点
    }
    dfs(1,1);//从1号节点，深度为1开始搜索
    cout<<Max;//输出最大值
    return 0;
}
/*
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
*/