字节跳动一面后端算法题记录
字节跳动一面后端算法题记录
1.求一棵树中任意两个节点之间经过的最少节点数（包括两个节点本身）
2.打家劫舍（leetcode）
面试总结，人身第一次视频面试真的太紧张了，平时会的脑袋都转不动。吸取教训，多参加练习，加油
#字节跳动##面经##算法工程师##校招#
2019-08-19 16:25 已编辑 华中师范大学 算法工程师
关注
全部评论
想去上海的小老弟
门头沟学院 Java
我之前是值最大最小的两节点距离，很类似😁
算法才是灵魂
百度_核心搜索部rank_算法工程师
贴一个第一题的解法吧：思路：求最近祖先，然后层次遍历，求路径长。下面是求路径，节点的话，再+1就行 class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
def countPath(node, a:int, b:int):
res = 0
stack = [node]
while len(stack) > 0:
tmp = []
while len(stack) > 0:
t = stack.pop()
if t == None:
continue
if t.val == a or t.val == b:
return res
tmp.append(t.left)
tmp.append(t.right)
stack = tmp
res += 1
return -float("inf")
def nodeDistances(root:None,a:int,b:int):
if root == None:
return None
if root.val == a or root.val == b:
return root
x = nodeDistances(root.left, a, b)
y = nodeDistances(root.right, a, b)
if x == None:
return y
elif y == None:
return x
else:
return root
if __name__ == "__main__":
root = nodeDistances(node, a, b)
if root.val == a or root.val == b:
print(max(countPath(root.left,a,b), countPath(root.right,a,b)) + 1)
else:
print(countPath(root.left,a,b) + countPath(root.right,a,b) + 2)
相关推荐
点赞 评论 收藏
分享
10-19 15:00
文华学院 嵌入式工程师 
点赞 评论 收藏
分享