菲斯不可新鲜面经

timeforce 发表于 2018-10-16 15:58
这里不是很明白，能举个例子么？

就比如我现在有一颗树，按照level order存在int[] 里面： [1, 2, 3, 4, #, 5, #], 然后在用hashmap 存每一个node的index值，然后每次有树的node进来就可以快速找到它的index， 然后通过index /2 不断找到它的parent，最先找到的共同的就是LCA。这样最多需要查找树的高度那么多次。如果是balanced tree的话，就是log n 了。

followup是用RMQ解决LCA问题的经典方法，大家可以gg一下：
1. Tarjan（离线）算法： 在一次遍历中把所有询问一次性解决，预处理时间复杂度O(nlogn),每次查询时间复杂度O(1)，总时间复杂度是O(nlogn+q)。
2. 倍增算法：利用二分两个节点同时往上走，直到相遇，预处理时间复杂度O(nlogn)，每次查询时间复杂度O(logn)，总时间复杂度O(nlogn+qlogn)。
3. RMQ算法

楼主你好~ 我现在也在team match的阶段，请问楼主现在进展怎么样了？可以交流一下吗？ 谢谢！

raymond_hr 发表于 2018-10-20 03:37
楼主你好~ 我现在也在team match的阶段，请问楼主现在进展怎么样了？可以交流一下吗？ 谢谢！

好啊，好啊。我私信你啦~

请问楼主第一题，能给一个“有一个treenode 不在树里 有LCA”的例子吗，不太懂，已加米