左孩子右兄弟

题目 左孩子右兄弟

思路分析

把最深的子树放在最右边（根节点的孩子数）才会使得全局最深

现在就是确定最深的子树是哪个 他们之间是互相独立的 所以可以递归去求 然后取个max

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int n;

int h[N],e[N],ne[N],idx;

void add(int a,int b){

    e[idx]=b,ne[idx]=h[a],h[a]=idx++;

}

int dfs(int u){

    int hmax=0,cnt=0;

    for(int i=h[u];i!=-1;i=ne[i]){

        int j=e[i];

        hmax=max(hmax,dfs(j));

        cnt++;

    }

    return hmax+cnt;

}

int main()

{

    cin>>n;

    memset(h,-1,sizeof h);

    for(int i=2;i<=n;i++){

        int p;

        cin>>p;

        add(p,i);

    }

    cout<<dfs(1);

    return 0;

}

同类题型

视频讲解

⬅️ 9、后缀表达式 🏠 00-刷题理模型 ➡️ 疑难杂类