关注
贴一个第一题的解法吧:思路:求最近祖先,然后层次遍历,求路径长。下面是求路径,节点的话,再+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个岗位 >
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
346839次浏览 7210人参与
# 你更愿意参加线上面试还是线下面试? #
4427次浏览 70人参与
# 晒一晒我的offer #
2759287次浏览 49449人参与
# 如何确定求职岗位 #
100664次浏览 2389人参与
# 华为求职进展汇总 #
432464次浏览 4346人参与
# 机械人怎么评价今年的华为 #
48852次浏览 398人参与
# 第一次面试 #
13529次浏览 206人参与
# 非技术岗薪资爆料 #
4530次浏览 95人参与
# 如果再来一次,你还会学硬件吗 #
16666次浏览 329人参与
# 海信求职进展汇总 #
6759次浏览 90人参与
# 通信硬件薪资爆料 #
136321次浏览 965人参与
# 来聊聊机械薪资天花板是哪家 #
17881次浏览 136人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
21979次浏览 211人参与
# 除了offer,现在你还缺点啥? #
1977次浏览 44人参与
# 应届生应该先就业还是先择业 #
10598次浏览 103人参与
# 百度工作体验 #
18940次浏览 205人参与
# 通信硬件人笔面经互助 #
62536次浏览 1392人参与
# 讲讲我经历过的年终奖 #
5788次浏览 76人参与
# 软件开发薪资爆料 #
533872次浏览 9198人参与
# 租房前辈的忠告 #
19680次浏览 1575人参与