VictriD's blog
victrid.dev
最近公共祖先 ( L owest C ommon A ncestor)的定义：同一棵树的节点u，v，定义: lca(u,v)为分别包含u、v的全部该树的子树的并集中的最小高度树的根节点。 下面介绍四种求最近公共祖先的方法。暴力法、倍增法、Tarjan算法，RMQ算法。 暴力法 标记现在的点访问过；向上跳到父节点。 重复这一过程，直到跳到的父节点被标记为访问过。 时间复杂度 O(n) (还需要 O(…
讨论
登录后参与讨论
还没有评论，来说第一句吧。