DOM 树的最近公共祖先
问题
给定一个 DOM 树和两个 DOM 节点，找到它们的最近公共祖先（Lowest Common Ancestor, LCA）。
示例：
<div id="root">
<div id="A">
<div id="C"></div>
<div id="D">
<div id="E"></div>
</div>
</div>
<div id="B">
<div id="F"></div>
</div>
</div>
findLCA(E, F) → root
findLCA(C, E) → A
findLCA(E, D) → D（D 是 E 的祖先，也是自身的最近公共祖先）
使用场景
- 事件委托中确定最近的共同容器
- 编辑器中选区的公共祖先（
Selection.getRangeAt()的commonAncestorContainer） - 组件通信时找共同的上下文 Provider
答案
方法一：使用 contains API（推荐）
findLCA.ts
function findLCA(node1: Node, node2: Node): Node | null {
// 从 node1 向上遍历，找到第一个包含 node2 的祖先
let current: Node | null = node1;
while (current) {
if (current.contains(node2)) return current;
current = current.parentNode;
}
return null; // 不在同一棵树
}
复杂度分析
- 时间复杂度： —
h1为 node1 的深度，contains最坏 - 实际上浏览器的
contains是 C++ 实现，非常快
方法二：路径比较法（通用，面试首选）
收集两个节点到根的路径，然后找最后一个相同的节点：
findLCAPath.ts
function findLCA(node1: Node, node2: Node): Node | null {
// 1. 收集 node1 到根的路径
const path1: Node[] = [];
let current: Node | null = node1;
while (current) {
path1.push(current);
current = current.parentNode;
}
// 2. 收集 node2 到根的路径
const path2: Node[] = [];
current = node2;
while (current) {
path2.push(current);
current = current.parentNode;
}
// 3. 从根开始比较，找最后一个相同的节点
path1.reverse();
path2.reverse();
let lca: Node | null = null;
const minLen = Math.min(path1.length, path2.length);
for (let i = 0; i < minLen; i++) {
if (path1[i] === path2[i]) {
lca = path1[i];
} else {
break;
}
}
return lca;
}
复杂度分析
- 时间复杂度： — 两次向上遍历
- 空间复杂度： — 存储路径
方法三：Set 查找法（空间换时间）
findLCASet.ts
function findLCA(node1: Node, node2: Node): Node | null {
// 1. 将 node1 的所有祖先放入 Set
const ancestors = new Set<Node>();
let current: Node | null = node1;
while (current) {
ancestors.add(current);
current = current.parentNode;
}
// 2. 从 node2 向上找，第一个在 Set 中的就是 LCA
current = node2;
while (current) {
if (ancestors.has(current)) return current;
current = current.parentNode;
}
return null;
}
复杂度：时间 ，空间
方法四：双指针（最巧妙， 空间）
类似「链表相交问题」的思路：
findLCATwoPointers.ts
function findLCA(node1: Node, node2: Node): Node | null {
let p1: Node | null = node1;
let p2: Node | null = node2;
// 两个指针交替遍历，最终会在 LCA 处相遇
while (p1 !== p2) {
p1 = p1 ? p1.parentNode : node2;
p2 = p2 ? p2.parentNode : node1;
}
return p1;
}
原理：
- p1 走完 node1 的路径后，从 node2 重新开始
- p2 走完 node2 的路径后，从 node1 重新开始
- 两者走过的总距离相等，最终在 LCA 处相遇
注意
这个方法假设两个节点在同一棵树中。如果不在，两个指针最终都会变成 null 而退出循环。
扩展：二叉树的 LCA (LeetCode 236)
面试中也可能考二叉树版本：
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val: number) {
this.val = val;
this.left = null;
this.right = null;
}
}
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode,
q: TreeNode
): TreeNode | null {
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 如果左右都找到了，说明当前节点就是 LCA
if (left && right) return root;
return left ?? right;
}
常见面试追问
Q1: DOM 中的原生 API 能否找到公共祖先？
答案：
// Selection API 中有 commonAncestorContainer
const selection = window.getSelection();
if (selection && selection.rangeCount > 0) {
const range = selection.getRangeAt(0);
const lca = range.commonAncestorContainer;
}
// 或者用 Node.contains()
document.body.contains(someNode); // true/false
// compareDocumentPosition 可以判断节点关系
const relation = node1.compareDocumentPosition(node2);
// DOCUMENT_POSITION_CONTAINS = 8
// DOCUMENT_POSITION_CONTAINED_BY = 16
Q2: 这题和 React 的 Context 有什么关系？
答案：React 的 Context 查找就是一个「向上查找最近祖先」的过程。useContext 会沿着 Fiber 树向上找最近的 Provider，原理类似于 DOM LCA。
Q3: 如果有多个节点（不只两个），如何找 LCA？
答案：两两求 LCA，逐步合并：
function findLCAMultiple(nodes: Node[]): Node | null {
if (nodes.length === 0) return null;
let lca: Node | null = nodes[0];
for (let i = 1; i < nodes.length; i++) {
lca = findLCA(lca!, nodes[i]);
if (!lca) return null;
}
return lca;
}