Apple 电面

分享一个这周的apple 电面。
          a
        /   \
       b    c
      /  \  /  \
    d     e    f

给定一个二叉树，其中有一个节点，例如上题中的e ，有两个父节点，找出该节点并修复二叉

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

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

补充内容 (2021-04-20 11:38 +8:00):
今天收到邮件通知，don't move forward。

求问楼主有消息了吗？我也是上周面的，到现在还没收到消息，担心会不会默剧啊

New_Pants 发表于 2021-4-20 02:08
求问楼主有消息了吗？我也是上周面的，到现在还没收到消息，担心会不会默剧啊

没有，我是上周三面的，静静地等待消息吧。祝我们好运。

楼主，这个follow up里环的情况用你本来的方法不是也可以解决么🤔？

如果这只是个BT而不是BST，是不是可能存在一个数字出现多次的情况呢，即使没有2个父节点

请问楼主的面的是哪个组？

Tre333 发表于 2021-4-21 09:24
请问楼主的面的是哪个组？

西雅图的siri 组

如果这个loop是指abec的话，那么在traversal的过程中用个hashset检查一下之前的node是否存在就可以，也就是第一问的解决方法。
第二问，如果是我，我会告诉他，在第一问的基础上，找到重复node的两个parents，然后通过找到这两个parent nodes的lowest common ancestor来找到loop入口。

至少第一问很简单，不就是搞个set呗，所以不知道为啥lz会被rej
另外第二问我没懂binary tree所谓的loop，指的是directed loop还是undirected loop？比如图里的情况，是有undirected loop的，但没有directed loop

补充内容 (2021-08-12 13:02 +8:00):
估计是undirected loop；所以union find check即可