小米笔试题-树的高度

import java.io.*;
import java.util.*;

import javax.naming.InterruptedNamingException;

public class Main
{
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	while (in.hasNext()) {
    		Map<Integer, Node> map = new HashMap<Integer, Node>();
    		Set<Integer> cSet = new HashSet<>();
    		ArrayList<Integer> rList = new ArrayList<>();
    		
    		int n = Integer.valueOf(in.nextLine());
    		for (int i = 0; i < n - 1; i++) {
    			String[] ss = in.nextLine().split("\\s");
    			int r = Integer.valueOf(ss[0]);
    			int c = Integer.valueOf(ss[1]);
    			
    			rList.add(r);
    			cSet.add(c);
    			Node node = map.get(r);
    			if (node == null) {
    				node = new Node();
    				node.left = c;
    				map.put(r, node);
    			} else {
					if (node.left == -1) 
						node.left = c;
					else 
						node.right = c;
				}
    		}
    		
    		//寻找根节点
    		int root = 0;
    		for (int i = 0; i < rList.size(); i++) {
    			if (!cSet.contains(rList.get(i))) {
    				root = rList.get(i);
    				break;
    			}
    		}
    		
    		//
    		System.out.println(root);
    		int h = height(root, map);
    		System.out.println(h);
    		
    		
    	}
    }
    
    public static int height(int root, Map<Integer, Node> map) {
    	Node node = map.get(root);
    	if (node == null) {
    		return 1;
    	}
    	int left = 0;
    	int right = 0;
    	if (node.left != -1) {
    		left = height(node.left, map);
    	}
    	if (node.right != -1) {
    		right = height(node.right, map);
    	}
    	int h = (left > right ? left : right) + 1;
    	return h;
    	
    }
}

class Node {
	public int left = -1;
	public int right = -1;
}


#百度#
全部评论
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:54
我写的跟楼主差不多啊 90%
点赞 回复 分享
发布于 2016-09-23 21:36
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] p = new int[n]; int[] l = new int[n]; int[] r = new int[n]; int root=0; for(int i=0;i<n;i++){ p[i]=-1; l[i]=-1; r[i]=-1; } for(int i=0;i<n-1;i++){ int tmpp = in.nextInt(); int tmpc = in.nextInt(); p[tmpc]=tmpp; if(l[tmpp]==-1)l[tmpp]=tmpc; else r[tmpp]=tmpc; } for(int i=0;i<n;i++){ if(p[i]==-1){ root=i; break; } } System.out.println(result(root,l,r)); } in.close(); } private static int result(int start, int[] l, int[] r){ if(l[start]==-1&&r[start]==-1)return 1; if(l[start]==-1&&r[start]!=-1)return 1+result(r[start],l,r); if(r[start]==-1&&l[start]!=-1)return 1+result(l[start],l,r); else return Math.max(1+result(r[start],l,r), 1+result(l[start],l,r)); } }
点赞 回复 分享
发布于 2016-09-23 21:08

相关推荐

点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务