4.7微软软件开发实习面经

45分钟一道题:在一个普通树里寻找m个节点的公共祖先
要求应该是只能遍历一次?
#微软#
全部评论
每个节点记录个值,一开始只有m个点的值为1,然后从下往上合并,深度最大值为m的就是了,类似于树上差分
1 回复 分享
发布于 2021-04-07 19:18
后续遍历用数组记录情况,如果m个节点没有重复的话也可以用int变量记录遇到了多少个。应该可以过
1 回复 分享
发布于 2021-04-07 17:32
后序递归 不知道是不是找最近公共
点赞 回复 分享
发布于 2021-04-21 14:56
可以用map记录[节点]=父节点,然后对这些节点在map里搜索公共父节点
点赞 回复 分享
发布于 2021-04-08 11:08

相关推荐

2025-11-28 16:00
已编辑
武汉理工大学 Java
点赞 评论 收藏
分享
评论
1
11
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务