笔试
3 分钟 读完 (大约 413 个字)

树的高度（小米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

×