【每日一题】左孩子右兄弟——21年省赛(JAVA解法)

简介: 对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵二叉树。如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。给定一棵包含 N​​ 个结点的多叉树,结点从 1 至 N​ 编号,其中 1 号结点是根,每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树,高度最高是多少。注:只有根结点这一个结点的树高度为 0​。

 题目链接:

题目描述

对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。

换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。

给定一棵包含 N 个结点的多叉树,结点从 1 至 N 编号,其中 1 号结点是根,每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树,高度最高是多少。

注:只有根结点这一个结点的树高度为 0。

输入描述

输入的第一行包含一个整数 N。 以下 N−1 行,每行包含一个整数,依次表示 2 至 N 号结点的父结点编号。

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

5
1
1
1
2

image.gif

输出

4

image.gif

代码:

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); //因为所在相同数组为兄弟,所以长度=父节点的个数+为兄弟的个数        }
    }
}

image.gif


相关文章
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
48 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
53 1
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
36 0
|
5月前
|
Java
杭电 OJ 1010-1019 Java解法(未更新完毕)
杭电 OJ 1010-1019 Java解法(未更新完毕)
26 1
|
5月前
|
Java
八皇后问题92种解法(java)
八皇后问题92种解法(java)
|
5月前
|
Java
杭电acm1201 18岁生日 Java解法 时间类
杭电acm1201 18岁生日 Java解法 时间类
24 0
|
5月前
|
算法 Java
杭电 OJ 1000-1009 Java解法
杭电 OJ 1000-1009 Java解法
22 0
|
5月前
|
Java
杭电acm2018 母牛的故事 Java解法 经典递归
杭电acm2018 母牛的故事 Java解法 经典递归
24 0