字节跳动一面后端算法题记录

字节跳动一面后端算法题记录
1.求一棵树中任意两个节点之间经过的最少节点数(包括两个节点本身)
2.打家劫舍(leetcode)

面试总结,人身第一次视频面试真的太紧张了,平时会的脑袋都转不动。吸取教训,多参加练习,加油
#字节跳动##面经##算法工程师##校招#
全部评论
我之前是值最大最小的两节点距离,很类似😁
点赞 回复
分享
发布于 2019-08-19 16:15
贴一个第一题的解法吧:思路:求最近祖先,然后层次遍历,求路径长。下面是求路径,节点的话,再+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)
点赞 回复
分享
发布于 2019-08-26 12:26
阿里巴巴
校招火热招聘中
官网直投

相关推荐

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