本文共 149 字，大约阅读时间需要 1 分钟。

只有一次查询：

递归处理，时间O(N)

频繁查询：

打出所有两两节点组合的哈希表，方便查询，时间O(N*N)

M次查询：

哈希+并查集，时间O(N+M)

思想，从下向上合并节点，每次依据左子树合并根节点，再合并右子树的顺序，只对新加入的节点考虑是否有对应查询，有的话返回并查集合并后的公共祖先即可。

转载地址：http://xbwji.baihongyu.com/