本文最后更新于 603 天前,其中的信息可能已经有所发展或是发生改变。
分析这个案例,大概可以得出在多叉树在变成二叉树时,无论变成怎么样的一个二叉树,只要这棵树最后一个节点的子节点个数最多的时候,整个二叉树高度最高,此时涉及到树的遍历,即树的DP,啊~好麻烦,思路大概是
我们用map来模拟邻接表操作存储树,表示树的子节点以及其孩子,其中key表示的是父节点,value表示为key的孩子 ,存储完树之后,开始寻找树的根节点的子节点最长的那条。于是有以下代码
故由此
import java.util.*; public class Main { //分析这个案例,大概可以得出在多叉树在变成二叉树时,最后一个节点的子节点个数 //最多的时候,整个二叉树高度最高,即height = size+max; static Map<Integer, List> map = new HashMap<Integer,List>(); public Main(int father, int current){ //我们用map来模拟邻接表操作存储树,表示树的子节点以及 //其孩子,其中key表示的是父节点,value表示为key的孩子 if (map.containsKey(father)){ //如果对邻接表标示树有疑问,需要补充数据结构的相关知识 map.get(father).add(current); }else{ map.put(father,new ArrayList()); map.get(father).add(current); } } public static int dfs(int i, Map<Integer,List> map){ // 这里我们用了树的遍历方式,即树形DP if (!(map.containsKey(i))) return 0; //当前节点的子树数量 int size = map.get(i).size(); //子树的子树的数量的最大值 int max = 0; //我们递归先访问到最底层的节点,再一步步的向上递归, //递归的过程总是难以理解,可以使用流程图去帮助理解 for (int j = 0;j<size;j++){ max = Math.max(dfs(map.get(i).get(j),map),max); } return size+max; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); map.put(1,new ArrayList()); int N = sc.nextInt(); for (int i = 2;i<N+1;i++){ new Main(sc.nextInt(),i); } System.out.println( dfs(1,map)); } }