【问题描述】
对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。注：只有根结点这一个结点的树高度为 0 。例如如下的多叉树：
可能有以下 3 种 (这里只列出 3 种，并不是全部) 不同的 “左孩子右兄弟”表示：
其中最后一种高度最高，为 4。
【输入格式】
输入的第一行包含一个整数 N。
以下 N −1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。
【输出格式】
输出一个整数表示答案。
【样例输入】
5
1
1
1
2
【样例输出】
4
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ N ≤ 20；
对于所有评测用例，1 ≤ N ≤ 100000。
解题思路：①看到树并且根据题意可以知道类似求最长路径，可以使用深度优先搜索dfs算法，即找节点的孩子，再继续找该孩子的孩子…直到没有再回退。②可以使用一个ArrayList数组来存储每个节点及其孩子（类似图的邻接表存储），也就是说ArrayList数组的元素也是ArrayList，每个ArrayList元素存储着该节点及其子孩子。
Java代码：
import java.util.ArrayList; import java.util.Scanner; public class Tree { 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); } } }
