谷歌onsite面经

jy_121 发表于 2019/04/04 02:20:49


请问下具体怎么做呢？谢谢

层次遍历的时候如果发现遇到已访问的说明就是多余的边了。然后删除这条边。

umialpha 发表于 2019-4-2 15:06
嗯嗯，给了root的话一个层次遍历（或者bfs）就ok了，感谢

二叉树多余一条边意思不是有至少一个节点有两个parent吗？删哪条边都不会影响树的高度啊

umialpha 发表于 2019-4-4 09:03
层次遍历的时候如果发现遇到已访问的说明就是多余的边了。然后删除这条边。

为什么这样remove后的tree就是高度最小的呢？

jy_121 发表于 2019-4-4 09:46
为什么这样remove后的tree就是高度最小的呢？

因为用层次遍历，每次访问新的节点就是新的一层，高度+1，如果你不去掉这一条边，而是去掉之前访问的那条边，那么高度肯定没有原来的小（最多是一样高）

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

umialpha 发表于 2019-4-4 09:48
因为用层次遍历，每次访问新的节点就是新的一层，高度+1，如果你不去掉这一条边，而是去掉之前访问的那条 ...

明白了，谢谢

lz可以讲下第四题怎么用拓扑排序吗

第四题是标准的 二分图最大匹配。匈牙利算法吧。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies