狗狗店面

lz继续攒rp

面的题好像在地里看过，给N条边代表二叉树的边，其中有且有一条边是多余的，请找出这条

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

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

Corner case非常多。但是也让过了，很神奇。

我想了一下大概可以这样做，不知道有什么corner case我没有考虑到：从所有的节点中不断任选一个做便利(dfs, bfs都可以), 在遍历过程中，如果遇到已经visited的点，那么这条边就是多余的。不断重复知道所有点都遍历完。

jiangsuliji 发表于 2017-10-6 05:24
这题是LC 684, 看了答案，用disjoint set union来解。。。

不一样，这个是有向边，而且是二叉树，684是无向边，啥树都可以

jiangsuliji 发表于 2017-10-6 05:24
这题是LC 684, 看了答案，用disjoint set union来解。。。

这题还有个II

请问楼主什么叫做多余的边

多余的边指除掉这条边就能形成一个valid二叉树。

感觉有点像207. Course Schedule

请问边是有方向性的吗?

请问楼主是phone interview吗？

这道题可以用bfs做吧？用set标记走过的点

楼主能不能讲下这题思路是用什么来做，是图吗

请问lz什么是有两个parent…? 没太理解这个corner case