【动态规划2】左孩子右兄弟

题目描述

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

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

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

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

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

注：只有根结点这一个结点的树高度为 00​。

输入描述

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

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

5
1
1
1
2

输出

4

评测用例规模与约定

对于 30%​​ 的评测用例，1≤N≤20​；

对于所有评测用例，1≤N≤100000。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

———————————————————————————————————————————

解析：这是一个动态规划问题。

 

         由上面的图可以看出，可以以2孩子作为左子树，也可以以3孩子作为左子树，还可以以4孩子作为左子树，其中高度最大的是把2孩子放在4孩子的位置转化成二叉树的树高最大。所以我们构造dp状态方程，假设dp[i]是以i号节点为根节点的子树的最大树高，则dp[1] = max(dp[2],dp[3],dp[4]).

（1）对于每个节点i，我们只考虑i节点和它的子节点，不考虑子节点的子节点。

（2）假设length（total,father）函数是用来求以father为父节点，和它的子节点构成的子树的最大高度。记住其中total并不是要求的最大高度，而是求之前的初始值。例如length(0,1)是用来求以1号节点为父节点，和2,3,4号节点构成的二叉树的最大高度。

（3）我们知道树-->二叉树，是把最左边的子节点作为左孩子，剩余的子节点作为左孩子的右孩子。例如2号节点作为左孩子，3,4作为2节点的右孩子。即以1节点作为根节点的二叉树的高度至少有3个单位（所有的直接子孩子个数和）。

（4）这是2,3,4的位置就决定了整棵树的树高，要想整棵树的高度尽可能的高，我们最好把2,3,4拥有子节点最多的那个节点放到最右边的位置（4的位置），因为这样转成二叉树后，这个节点位于二叉树的右下角。这样的结构使得树的高度最高。

总结：

        绿色部分是固定死的，1和2,3,4构成树的最小树高，接下来想使得整棵树尽可能高，只要把拥有子节点最多的字节放到最右边节点的位置上，这样这个节点的子节点都可以用来增加树高。

import java.awt.print.Printable;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
 
 
public class Main {
	
	public static int result = 0;
	public static ArrayList<Integer>[] lists = null;
	
	//求以父节点为根节点，直接子节点为孩子的二叉树的最大高度
	public static void search(int init,int fatherNode) {
		int hight = lists[fatherNode].size();
		
		if(hight == 0) {
			result = Math.max(init, result);
			return;
		}
		
		int nowHight = init + hight;
		for(int temp :  lists[fatherNode]) {
			search(nowHight,temp);
		}
		
		
	}
 
	public static void main(String[] args) {
		
		//System.out.println("请输入数据");
		Scanner scan = new  Scanner(System.in);
		
		int nodeNumber;
		
		//输入总的节点数
		nodeNumber = scan.nextInt();
		
		//构造邻接表,创建ArrayList数组
		lists = new ArrayList[nodeNumber+10];
		
		//每个lists[i]都是存储一个ArrayList
		for(int i = 1;i<=nodeNumber;i++) {
			lists[i] = new ArrayList<Integer>();
		}
		
		//写入邻接表
		for(int j = 2;j<=nodeNumber;j++) {
			int node = scan.nextInt();
			lists[node].add(j);
		}
		
		search(0,1);
		System.out.println(result);
		
		scan.close();
 
	}
	
}