小米笔试题-树的高度

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;
}