首页 > 代码库 > 输入N组父子对，求父子对所组成的二叉树的高度----17年某公司的笔试题
输入N组父子对，求父子对所组成的二叉树的高度----17年某公司的笔试题
题目的大致意思如下：
输入N组数，一组数代表一个父子对（如，0 1,0代表父节点，1代表子节点），求这N组数所组成的二叉树的高度；
例如：
输入：6
0 1
0 2
1 3
1 4
2 5
3 6
输出：4
解题思路：两种方法，动态规划和回溯法
一.动态规划法：使用一个数组hight[N]记录每组数所能组成的二叉树的高度,初始化为全1数组，使用一个数组visited[N]来记录每组数的访问情况，找出最优子结构：
当visited[i]=0时，visited[i]=1,hight[i] = hight[i]+1;
然后，当matrix[j][0]=matrix[i][1]且visited[j]=0时，hight[j] = hight[i]+1，visited[j]=1;
代码如下：
import java.util.Scanner;public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int groups = scanner.nextInt(); int[][] matrix = new int[groups][2];for(int i=0;i<groups;i++){ for(int j=0;j<2;j++){ matrix[i][j] = scanner.nextInt(); } }
//动态规划输出处理
System.out.println(maxHightHelper(matrix));
} }//动态规划 public static int maxHightHelper(int[][] matrix){ if(matrix==null||matrix.length==0) return 0; //记录当前组的高度 int[] hight = new int[matrix.length]; for(int i=0;i<hight.length;i++) hight[i] = 1; byte[] visited = new byte[matrix.length]; for(int i=0;i<matrix.length;i++){ if(visited[i]==0){ visited[i] = 1; hight[i] = hight[i]+1; } for(int j=i+1;j<matrix.length;j++){ if(matrix[j][0]==matrix[i][1]&&visited[j]==0){ visited[j] = 1; hight[j] = hight[i] +1; } } } //找最大的高度 int max = 0; for(int i=0;i<hight.length;i++){ if(max<hight[i]) max = hight[i]; } return max; }}
二.回溯法：待会补充
输入N组父子对，求父子对所组成的二叉树的高度----17年某公司的笔试题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。