面试中，经常遇到的一个简单算法题：查找两个单链表的公共节点最近在读 react 源码的时候发现一个 react 树中对该算法的运用（见 getLowestCommonAncestor 函数），在此做简单的记录。git 地址
getParent
在 react 树中获取当前实例节点的父节点实例
//HostComponent 组件对应的 DOM，比如 App 的 tag=3, 表示为类组件，其 child 为 tag= 5 对应 div 元素。
function getParent(inst) {
do {
inst = inst.return;
// TODO: If this is a HostRoot we might want to bail out.
// That is depending on if we want nested subtrees (layers) to bubble
// events to their parent. We could also go through parentNode on the
// host node but that wouldn’t work for React Native and doesn’t let us
// do the portal feature.
} while (inst && inst.tag !== HostComponent);
if (inst) {
return inst;
}
return null;
}
getLowestCommonAncestor
获取节点 A 与 B 的最近的公共祖先节点
算法题：找到两个链表的公共节点
export function getLowestCommonAncestor(instA, instB) {
// 获取子节点 A 在树中的深度
let depthA = 0;
for (let tempA = instA; tempA; tempA = getParent(tempA)) {
depthA++;
}
// 获取子节点 B 在树中的深度
let depthB = 0;
for (let tempB = instB; tempB; tempB = getParent(tempB)) {
depthB++;
}
// If A is deeper, crawl up.
// 如果 A 的高度高，那么 A 节点先往上走 depthA – depthB 个节点，最后同时走，直到父节点是同一个
while (depthA – depthB > 0) {
instA = getParent(instA);
depthA–;
}
// 如果 B 的高度高，那么 B 节点先往上走 depthB – depthB 个节点，最后同时走，直到父节点是同一个
// If B is deeper, crawl up.
while (depthB – depthA > 0) {
instB = getParent(instB);
depthB–;
}
// Walk in lockstep until we find a match.
// 现在，指针所处的位置的高度一致，可以同时往上查找，直到找到公共的节点
let depth = depthA;
while (depth–) {
if (instA === instB || instA === instB.alternate) {
return instA;
}
instA = getParent(instA);
instB = getParent(instB);
}
return null;
}
isAncestor
判断 A 节点是否是 B 节点的祖先节点
export function isAncestor(instA, instB) {
while (instB) {
if (instA === instB || instA === instB.alternate) {
return true;
}
instB = getParent(instB);
}
return false;
}
getParentInstance
对 getParent 的 export 封装：
export function getParentInstance(inst) {
return getParent(inst);
}
traverseTwoPhase
对 inst 及其以上的树执行冒泡捕获的操作，执行 fn。类似事件的冒泡捕获
export function traverseTwoPhase(inst, fn, arg) {
const path = [];
// 将 inst 的父节点入栈，数组最后的为最远的祖先
while (inst) {
path.push(inst);
inst = getParent(inst);
}
let i;
// 从最远的祖先开始向 inst 节点捕获执行 fn
for (i = path.length; i– > 0;) {
fn(path[i], ‘captured’, arg);
}
// 从 inst 节点开始向最远的祖先节点冒泡执行 fn
for (i = 0; i < path.length; i++) {
fn(path[i], ‘bubbled’, arg);
}
}
traverseEnterLeave
当关注点从 from 节点移出然后移入 to 节点的时候, 在 from 执行执行类似移入移出的操作,from 节点
export function traverseEnterLeave(from, to, fn, argFrom, argTo) {
const common = from && to ? getLowestCommonAncestor(from, to) : null;
const pathFrom = [];
while (true) {
if (!from) {
break;
}
if (from === common) {
break;
}
const alternate = from.alternate;
if (alternate !== null && alternate === common) {
break;
}
pathFrom.push(from);
from = getParent(from);
}
const pathTo = [];
while (true) {
if (!to) {
break;
}
if (to === common) {
break;
}
const alternate = to.alternate;
if (alternate !== null && alternate === common) {
break;
}
pathTo.push(to);
to = getParent(to);
}
// 以上代码将 from 节点到 from 与 to 节点的最近公共祖先节点（不包括公共祖先节点）push 到 pathFrom 数组
// 以上代码将 to 节点到 from 与 to 节点的最近公共祖先节点（不包括公共祖先节点）push 到 pathTo 数组
// 以下代码用于对 pathFrom 冒泡，执行 fn
for (let i = 0; i < pathFrom.length; i++) {
fn(pathFrom[i], ‘bubbled’, argFrom);
}
// 以下代码用于对 pathTo 捕获，执行 fn
for (let i = pathTo.length; i– > 0;) {
fn(pathTo[i], ‘captured’, argTo);
}
}