本文共 3199 字，大约阅读时间需要 10 分钟。

题目描述

现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度

输入描述:

输入的第一行表示节点的个数n（1 ≤ n ≤ 1000，节点的编号为0到n-1）组成，下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出描述:

输出树的高度，为一个整数

示例1

输入

复制

50 10 21 31 4

输出

复制

3

解题思路：

这是有个坑是题目要求为合法的二叉树，但输入数据是可以构成多叉树的，所以多余两个的子结构丢弃不用。

使map存储父结点和子结占的关系，然后从根结点进行遍历。

import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Scanner;import java.util.Set;public class Main {	public static int height;	public static void main(String[] args) {		// TODO Auto-generated method stub		Scanner sc = new Scanner(System.in);		Map
   
    > map = new HashMap
    
     >();		Set
     
       child = new HashSet
      
       ();		String line = "";		sc.nextLine();		while (sc.hasNextLine()) {			line = sc.nextLine();			if (line.length() < 2) {				break;			}			String[] items = line.split(" ");			int key = Integer.parseInt(items[0]);			int value = Integer.parseInt(items[1]);			if (map.containsKey(key)) {				if (map.get(key).size() < 2) {					map.get(key).add(value);				}			} else {				List
       
         list = new ArrayList
        
         (); list.add(value); map.put(key, list); } child.add(Integer.parseInt(items[0])); } int root = 0; for (Integer k : map.keySet()) { if (!child.contains(k)) { root = k; break; } } get(map, child, root, 0); System.out.println(height); } private static void get(Map
         
          > map, Set
          
            child, int root, int h) { // TODO Auto-generated method stub h++; if (map.get(root) == null) { if (h > height) { height = h; System.out.println("h: " + h + ", " + root); } } else { List
           
             list = map.get(root); for (Integer integer : list) { get(map, child, integer, h); } } }}
           
          
         
        
       
      
     
    
   

上面这个方法是个笨办法。

老干部使用了一种只记录结点所在深度的方法。但他的代码是在做平安笔试的时候写的，平安的题与这一题有点点区别。输入的时间没有第一行，也就是没有结点个数。而且老干部的解法没有考虑二叉树的合法验证。放在这里供自己学习。

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Scanner;public class Main {	public static void main(String[] args) {		// TODO Auto-generated method stub		Scanner in = new Scanner(System.in);		List
   
     items = new ArrayList
    
     ();		Map
     
       m = new HashMap
      
       ();		while(in.hasNextLine()) {			items.add(new MM(in.nextInt(),in.nextInt()));			in.nextLine();		}		if(items.size()>0) {			m.put(items.get(0).m, 0);			m.put(items.get(0).n, 1);		}		int i = 0;		while(items.size()!=0) {			i = i %items.size();			if(m.containsKey(items.get(i).m) && !m.containsKey(items.get(i).n)) {				m.put(items.get(i).n, m.get(items.get(i).m)+1);				items.remove(i);				continue;			}			if(!m.containsKey(items.get(i).m) && m.containsKey(items.get(i).n)) {				m.put(items.get(i).m, m.get(items.get(i).n)-1);				items.remove(i);				continue;			}			if(m.containsKey(items.get(i).m) && m.containsKey(items.get(i).n)) {				items.remove(i);				continue;			}			i++;		}		Integer[] nn = new Integer[m.size()];		nn =  m.values().toArray(nn);		List
       
         ll = Arrays.asList(nn);		Collections.sort(ll);		int result = ll.get(ll.size()-1)-ll.get(0)+1;		System.out.println(result);			}}class MM {	public int m;	public int n;	public MM(int m,int n) {		this.m = m;		this.n = n;	}}