---
title: "左孩子右兄弟"
created: 2025-11-28
tags:
  - 算法
---

# 左孩子右兄弟

## 题目 [左孩子右兄弟](https://www.acwing.com/problem/content/description/3425/)

![[image-5574c358.png]]

## 思路分析

![[image-09ab7468.png]]

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

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

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/疑难杂类/9、后缀表达式|9、后缀表达式]] 🏠 [[00-刷题理模型]] ➡️ [[疑难杂类|疑难杂类]]