小米笔试题-树的高度
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; }
#百度#