贴个简单的面经

原帖地址:mitbbs

第一轮一小时面试,白板题:
Binary Tree 里有重复的值,只会出现当前点的右侧,怎么删掉

有几个解法:
1. O(nlgn) time, O(1) space,从每个点开始遍历右边,删掉重复点
2. O(n) time, O(n) space,建map
3. O(n) time, O(1) space,Morris Traversal

最好的解法自然是3,但还是紧张,第一反应是解法1
写完聊天的时候说有一个解法是线性时间,常量空间的时候突然想起来,感觉自己略蠢