linkedin 码工 店面

奉献一个刚结束的linkedin的电话面试，居然不是leetcode题。

Given a

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

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

est to the target

这个题我只能想到brute force, 除了遍历整棵树 O(N). 能利用上BST的特性，更快吗？

补充内容 (2017-8-4 08:24):
看了一下log(N)的解法，Hard级别。 O(N)倒是容易想到，得看面试官的要求了。 https://discuss.leetcode.com/top ... acks-following-hint

重新看了一遍，居然是leetcode 272. 差别就是double 和int。。。。tag是google，不是linkedin的。

是题库里面的题，不过logN解法极其蛋疼，估计n 就好了

这道题leetcode上讨论得分最高解的思路是：
维护两个栈，一个放前驱序列，一个放后继序列。也就是把树对应的inorder序列（因为是BST，所以有序）拆两半，一半放比target大的，一个放比target小的（等于target的可以放在任意一边）。用栈保证栈顶是离target最近的。
然后循环比较栈顶，最接近target的进入结果集。