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