树的高度（小米2017秋招真题）

题目

题目描述

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

时间限制
C/C++语言：1000MS 其它语言：3000MS

内存限制
C/C++语言：65536KB 其它语言：589824KB

输入

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

输出

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

样例输入

样例输出

题解

java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] parent = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }

        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            parent[b] = a;
        }

        int h = 0;
        for (int i = 0; i < n; i++) {
            int max = 1;
            int j = i;
            while (parent[j] != -1) {
                j = parent[j];
                max++;
            }
            h = max > h ? max : h;
        }
        System.out.println(h);
    }
}

python

import sys

def get(x):
    try:
        return 1 + get(dic_s[x])
    except KeyError:
        return 1

n = int(sys.stdin.readline().strip())
dic_s = {}
for i in range(int(n)-1):
    j_1,j_2 = sys.stdin.readline().strip().split()
    dic_s[j_2] = j_1
print max([get(i) for i in set(dic_s.keys()) - set(dic_s.values())]) if n>1 else 1

javascript

var n=readInt(),rec={},dps={},rs=1
while(n-->1) {
  var a=readInt(),b=readInt()
  rec[a]=rec[a]||[]
  rec[a].push(b)
}
for(var k in rec) rs=Math.max(rs,maxDps(k))
print(rs)
function maxDps(n){
  if(!rec[n]) return 1
  if(dps[n]) return dps[n]
  var r=1
  for(var x of rec[n]) r=Math.max(r,maxDps(x)+1)
  dps[n]=r
  return dps[n]
}