LCA算法讲解及代码｜海量图解竞赛刷题（进阶篇）

最近公共祖先（Lowest Common Ancestors，LCA）是指有根树中距离两个节点最近的公共祖先。在树中，祖先是指从当前节点到树根路径上的所有节点。两个节点的公共祖先指的是一个节点既是第一个节点的祖先，又是第二个节点的祖先。而最近公共祖先是指距离两个节点最近的共同祖先。 LCA算法可用于求解树上任意两点之间的距离。假设我们需要求解节点u和v之间的距离，假设它们的最近公共祖先为lca。根据树的性质，u和v之间的距离等于u到根节点的距离加上v到根节点的距离减去2倍的lca到根节点的距离。 在LCA算法中，可以使用多种不同的方法进行求解。下面将介绍一种基于树的深度和父节点的LCA算法。 首先，我们需要预处理树中节点的深度和父节点信息。深度可以通过DFS（深度优先搜索）计算，父节点信息可以通过DFS过程中记录。 接下来，我们可以通过两个节点的深度信息来对齐它们的深度。假设节点u的深度大于节点v的深度，我们就将节点u向上移动到与节点v的深度相同的位置。 然后，我们不断地将节点u和v同时向上移动，直到它们的父节点相同。这个共同的父节点就是u和v的最近公共祖先。 最后，我们可以根据最近公共祖先和根节点的距离，计算出u和v之间的距离。 以下是使用Python实现的LCA算法的伪代码： ``` class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def build_parent_and_depth(root, parent, depth): if root: depth[root.val] = depth[parent[root.val]] + 1 build_parent_and_depth(root.left, parent, depth) build_parent_and_depth(root.right, parent, depth) def lowestCommonAncestor(root, p, q): parent = {} # 记录每个节点的父节点 depth = {None: -1} # 记录每个节点的深度，根节点的深度为0 parent[root.val] = None build_parent_and_depth(root, parent, depth) while p != q: if depth[p.val] < depth[q.val]: p, q = q, p p = parent[p.val] return p ``` 在以上代码中，我们首先定义了一个TreeNode类，用于表示树的节点。接着，我们定义了一个辅助函数`build_parent_and_depth`，用于递归地构建节点的深度和父节点信息。 然后，我们定义了一个`lowestCommonAncestor`函数，该函数接收树的根节点以及需要找到最近公共祖先的两个节点p和q。在该函数中，我们首先初始化了`parent`和`depth`字典，并分别将根节点的父节点初始化为None，根节点的深度初始化为0。 接下来，我们通过调用`build_parent_and_depth`函数来构建每个节点的父节点和深度信息。 最后，我们进入一个循环，不断比较节点p和节点q的深度。如果节点p的深度小于节点q的深度，我们就交换它们的位置。然后，我们将节点p向上移动到它们的深度相同的位置。接着，我们将节点p和节点q同时向上移动，直到它们的父节点相同。最终，我们返回它们的公共父节点作为最近公共祖先。 通过以上的LCA算法，我们可以很方便地求解树中任意两个节点的最近公共祖先，并计算它们之间的距离。这对于解决一些相关的问题，如树上两节点的最短路径等，非常有帮助。