小米笔试！！！求树的深度，全部AC，构建树-->求树的深度

import java.util.Scanner;

class TNode{
	private int value;
	public TNode left = null;
	public TNode right = null;
	
	public TNode(int i){
		this.value = i;
	}
}
public class xiaomi3 {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int nodeNum = scanner.nextInt();
			TNode[] treeNodes = new TNode[nodeNum];
			for(int i = 0; i < nodeNum; i++)
				treeNodes[i] = new TNode(i);
			for(int i = 0; i < nodeNum - 1; i++){
				int row = scanner.nextInt();
				int col = scanner.nextInt();
				if(treeNodes[row].left == null)
					treeNodes[row].left = treeNodes[col];
				else
					treeNodes[row].right = treeNodes[col];
			}
			int max = 0;
			for(int i = 0; i < nodeNum; i++){
				int height = getMaxDepth(treeNodes[i]);
				if(height > max)
					max = height;
			}
			System.out.println(max);
		}
	}
	
	// 获取最大深度
    public static int getMaxDepth(TNode root) {
        if (root == null)
            return 0;
        else {
            int left = getMaxDepth(root.left);
            int right = getMaxDepth(root.right);
            return 1 + Math.max(left, right);
        }
    }
}

坑就是在于根节点的不一定。

#小米#

全部评论

推荐最新楼层

神様

杭州电子科技大学 Java

import java.util.Scanner; class Main{ public static void main(String[] args) { Scanner in= new Scanner(System.in); while(in.hasNext()){ int n = in.nextInt(); int[] tree = new int[n]; for (int i = 0; i < tree.length; i++) { tree[i]=-1; } for(int i =0;i<n-1;i++){ int p = in.nextInt(); int c = in.nextInt(); tree[c] =p; } int max=1; int count =0; for (int i = n-1; i >0; --i) { int cur=i; while(cur!=-1) { cur = tree[cur]; count++; } if(count>max) max =count; count=0; } System.out.println(max); } } }

点赞回复分享

发布于 2016-09-23 21:25

这是昵称

重庆邮电大学前端工程师

点赞回复分享

发布于 2016-09-24 10:36

codingstar

钉钉信息_高级前端开发工程师

这道题可以用递归做吗？我用递归做就RE了，70%，突然想到可以用非递归的方式实现dfs……傻了…

点赞回复分享

发布于 2016-09-24 10:23

Riosngdfleiw1965

中央音乐学院 PHP

//树的深度 import java.util.*; public class Main{ public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin=new Scanner(System.in); int[] nn= new int[1001]; int i=0; int n=0; int count = cin.nextInt(); nn[i++] = count; while((count--)!=0) { n=cin.nextInt(); nn[i++]=n; } getlength(nn,i); } public static void getlength(int[] nn,int i){ int number = i-1; if(number==0){System.out.print(0);return;} else if(number==1){System.out.print(1);return;} else if(number>1&&number<5){System.out.print(2);return;} int start = 1; int censhu = 0; censhu = number/2; int hehe[][] = new int[censhu][2]; for(int i1=0;i1<censhu;i1++){ for(int j1=0;j1<2;j1++){ hehe[i1][j1] = nn[start]; start++; } } int maxlength1 = 2; for(int i2=0;i2<censhu-1;i2++){ for(int j2=i2+1;j2<censhu;j2++){ if(hehe[i2][1]==hehe[j2][0]){ maxlength1++; i2 = j2; } } } int maxlength2 = 2; for(int i3=1;i3<censhu-1;i3++){ for(int j3=i3+1;j3<censhu;j3++){ if(hehe[i3][1]==hehe[j3][0]){ maxlength2++; i3 = j3; } } } int maxlength = 0; if(maxlength1>maxlength2){ maxlength = maxlength1; }else{ maxlength = maxlength2; } System.out.print(maxlength); } }

点赞回复分享

发布于 2016-09-23 22:20

RoyK

西北工业大学 C++

感觉这道题没这么复杂吧，建一个列数组，从最低下记录每行的高度，查表一直递推上去就行了。

点赞回复分享

发布于 2016-09-23 22:04

mebixus

中国科学院大学安卓

楼主没有对输入数据的正确性进行检查就AC了么？我的代码和你的基本一样，但是没检查只有10%，检查之后才70%

点赞回复分享

发布于 2016-09-23 21:59

dandelionxxj

东南大学前端工程师

楼主，我也是这么想的，怎么还是10%,你帮我看看，谢谢 public class xiaomi2 { public static void main(String[] args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()){ int n=cin.nextInt(); if(n<1||n>1000){ throw new RuntimeException("error"); } List<myTree> list=new ArrayList<myTree>(); for(int i=0;i<n;i++){ list.add(new myTree(i)); } for(int i=0;i<n-1;i++){ int parent=cin.nextInt(); int child=cin.nextInt(); if((parent==child)||(parent>n-1)||(parent<0)||(child>n-1)||(child<0)){ throw new RuntimeException("error"); } if(parent>=0&&parent<n&&child>=0&&child<n){ if(list.get(parent).left==null) { list.get(parent).left=list.get(child); }else if(list.get(parent).right==null){ list.get(parent).right=list.get(child); }else { throw new RuntimeException("error"); } } } int max=0; for(int i=0;i<n;i++){ int high=getTreeHigh(list.get(0)); if(high>max) max=high; } System.out.println(max); } } private static int getTreeHigh(myTree myTree) { if(myTree==null) return 0; int left=getTreeHigh(myTree.left); int right=getTreeHigh(myTree.right); return left>=right?(left+1):(right+1); } } class myTree{ private int val; myTree(int i){ this.val=i; } public myTree left=null; public myTree right=null; }

点赞回复分享

发布于 2016-09-23 21:53