树的高度(小米2017秋招真题)

image.png

树的高度(小米2017秋招真题)

题目

题目描述

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

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

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

输入

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

输出

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

样例输入

1
2
3
4
5
5
0 1
0 2
1 3
1 4

样例输出

1
3

题解

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×