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

贴一个第一题的解法吧：思路：求最近祖先，然后层次遍历，求路径长。下面是求路径，节点的话，再+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)

我之前是值最大最小的两节点距离，很类似😁