多个节点怎么找到最近的公共父节点 根据id 和parent_id js
时间: 2024-09-13 13:06:34 浏览: 26
在JavaScript中,可以通过递归函数来查找多个节点的最近公共父节点。首先,你需要有一个节点的数据结构,其中每个节点包含一个唯一的`id`和一个指向其父节点的`parent_id`。下面是一个简单的算法步骤:
1. 创建一个函数`findClosestCommonAncestor`,接收两个节点的ID作为参数。
2. 创建一个辅助函数`tracePathToRoot`,该函数接收一个节点和目标祖先节点的ID,向上追溯直到找到该祖先节点,返回到达该祖先节点的路径。
3. 对于两个节点,分别调用`tracePathToRoot`函数,直到找到一个共同的祖先节点。
4. 这个共同的祖先节点就是它们的最近公共父节点。
这里是一个简单的代码示例:
```javascript
function tracePathToRoot(node, targetId, path = []) {
if (node.id === targetId) {
return path;
}
if (node.parent_id) {
path.push(node.id);
return tracePathToRoot(findNodeById(node.parent_id), targetId, path);
}
return null; // 没有找到路径
}
function findClosestCommonAncestor(id1, id2, nodes) {
const path1 = tracePathToRoot(findNodeById(id1, nodes), id2);
const path2 = tracePathToRoot(findNodeById(id2, nodes), id1);
let commonAncestor = null;
for (const ancestorId of path1) {
if (path2.includes(ancestorId)) {
commonAncestor = findNodeById(ancestorId, nodes);
break;
}
}
return commonAncestor;
}
function findNodeById(targetId, nodes) {
return nodes.find(node => node.id === targetId);
}
// 示例节点数据
const nodes = [
{ id: 'A', parent_id: null },
{ id: 'B', parent_id: 'A' },
{ id: 'C', parent_id: 'A' },
{ id: 'D', parent_id: 'B' },
{ id: 'E', parent_id: 'C' },
];
// 查找最近公共父节点
const ancestor = findClosestCommonAncestor('D', 'E', nodes);
console.log(ancestor); // 输出最近公共父节点的信息
```