Mic*_*ael
3
algorithm
least-common-ancestor
有时候我遇到的面试问题就像这样:"查找在树中的任何2个节点的公共父".我注意到他们也在谷歌,亚马逊等地提出了LCA问题.
正如维基百科所说, LCA可以通过从给定节点到根的路径的交集来找到,它需要O(H),其中H是树的高度.此外,还有更先进的算法可以在O(N)中处理树,并在O(1)中回答LCA查询.
我想知道访问者究竟想要了解候选人提出这个LCA问题的原因.路径交集的第一个算法似乎微不足道.他们是否希望候选人记住预处理算法？他们是否希望候选人能够即时发明这些算法和数据结构？