京东算法笔试:第一题
左右子树中,每次都只能从门口走一个人,因此只需要分别统计左右子树的值,然后取最大值;
对于左子树和右子树,每次分别只能出去一个人,因此实际上就是统计子树的节点数目,减一就可以。
个人理解的思路是这样,望指正...
from collections import deque
# n = int(input())
# # 建立一个二维数组存储 n-1 条边
# graph = []
# for i in range(n-1):
# list1 = list(map(int, input().split()))
# graph.append((list1[0], list1[1]))
n = 7
graph = [(2, 1), (3, 2), (5, 2), (4, 3), (6, 1), (8, 6)]
print(graph)
# 对边按照父亲节点进行排序
graph.sort(key=lambda x: x[1])
print(graph)
index = 0
door = []
while index < n - 1:
# 当前能直接出去的节点
if (graph[index][1] == 1):
door.append(graph[index][0])
else:
break
index += 1
ans = 0
for item in door:
queue1 = deque()
queue1.append(item)
cnt = 1
while(queue1):
temp = queue1.popleft()
for i in range(n-1):
if(graph[i][1] == temp):
cnt += 1
queue1.append(graph[i][0])
ans = max((ans, cnt))
print(ans)
#京东##笔试题目##题解##实习##春招#