京东算法笔试:第一题

左右子树中,每次都只能从门口走一个人,因此只需要分别统计左右子树的值,然后取最大值;
对于左子树和右子树,每次分别只能出去一个人,因此实际上就是统计子树的节点数目,减一就可以。
个人理解的思路是这样,望指正...


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)
#京东##笔试题目##题解##实习##春招#
全部评论
ac了?
点赞 回复
分享
发布于 2019-04-13 22:08
没说是二叉树
点赞 回复
分享
发布于 2019-04-13 22:09
阿里巴巴
校招火热招聘中
官网直投
边有说第二个一定是父节点吗?如果说了,这样应该是可以的吧。如果AC了,说明默认第二个是父节点。
点赞 回复
分享
发布于 2019-04-13 22:18
def findtime(newdict): if len(newdict)<=1: return 1 time=0 while len(newdict)>1: delete={} for key in newdict: if newdict[key][-1]==1: delete[key]=-1 new_del=list(delete.keys()) for key in newdict: if newdict[key][-1] in delete: if delete[newdict[key][-1]]==-1: delete[newdict[key][-1]] = key newdict[key] = [newdict[key][0], 1] else: newdict[key]=[newdict[key][0],delete[newdict[key][-1]]] for d in new_del: newdict.pop(d) time+=1 if len(newdict)==1: time+=1 return time
点赞 回复
分享
发布于 2019-04-13 23:49

相关推荐

点赞 6 评论
分享
牛客网
牛客企业服务