题目链接：
题目描述
对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
注：只有根结点这一个结点的树高度为 0。
输入描述
输入的第一行包含一个整数 N。 以下 N−1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。
输出描述
输出一个整数表示答案。
输入输出样例
示例 1
输入
5 1 1 1 2
输出
4
代码：
import java.util.ArrayList; import java.util.Scanner; public class 左孩子右兄弟 { static int res = 0; //结果（最高树高） static ArrayList<Integer>[] lists; //存储节点及其子孩子（类似一个邻接表） public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); lists = new ArrayList[n+1]; //后面我们是从下标1开始存储，因此这里不要忘记+1 //初始化（相当于填充进每个节点，数组下标即为该节点编号） for (int i = 1; i < n+1; i++) { lists[i] = new ArrayList<Integer>(); } //构建邻接表，将每个节点的孩子放到该下标的ArrayList里 for (int i = 2; i < n+1; i++) { int node = scanner.nextInt(); lists[node].add(i); } //从节点1（即根节点）开始dfs即可访问全部，因为这是一棵树 dfs(0,1); System.out.println(res); } //深度优先搜索dfs public static void dfs(int total, int father){ //递归寻找子节点的兄弟 //获取当前节点孩子个数 int size = lists[father].size(); //如果当前节点没有孩子，则重置res并返回 if (size == 0) { res = Math.max(res,total); return; } //对该节点的孩子依次进行dfs for (int temp : lists[father]){ dfs(total+size,temp); //因为所在相同数组为兄弟，所以长度=父节点的个数+为兄弟的个数 } } }
