如何用JS递归实现非二叉树的最近公共祖先(LCA)查找

核心思路 #

• 首先提取整棵树的全局最小值、最大值作为待查找的两个目标节点标识
• LCA判定逻辑：对于任意节点，若两个目标值分别落在该节点的不同子树中，或其中一个目标值属于当前节点本身，且所有下层子节点都不满足该条件，则当前节点就是最近公共祖先
• 全程仅使用map、reduce、filter等数组方法实现，符合禁用循环、forEach的要求

原有代码问题说明 #

• 原有findPath方法仅做了节点value的嵌套收集，未做LCA的匹配判定，返回结果为嵌套数组，不符合需求
• 未实现递归终止优化，找到LCA后仍会无差别遍历所有节点，性能较差

完整实现代码 #

const tree = {
children: [ 
    { 
        children: [
            { 
                children: [],
                values: [15.667786122807836]
            }
        ],
        values: [35.77483035532576, 1.056418140526505]
    },
    {
        children: [
            {
                children: [
                    {
                        children: [],
                        values: [67.83058067285563]
                    }
                ],
                values: [98.89823527559626]
            }
        ],
        values: [51.49890385802418, 41.85766285823911]
    },
],
values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};

// 保留原有极值提取逻辑
const min = graph => {
  return Math.min(...graph.values, ...graph.children.map(graphNode => min(graphNode)));
};

const max = graph => {
  return Math.max(...graph.values, ...graph.children.map(graphNode => max(graphNode)));  
};

// 递归查找LCA的核心方法
const findLCA = (node, target1, target2) => {
  // 统计当前节点匹配的目标数量
  const currentMatch = [target1, target2].filter(t => node.values.includes(t)).length;
  // 汇总所有子节点的递归结果
  const childResult = node.children.reduce((res, child) => {
    // 子树已找到LCA则直接返回，跳过剩余节点遍历
    if (res.lca) return res;
    const [childMatch, childLCA] = findLCA(child, target1, target2);
    if (childLCA) return { matchCount: res.matchCount + childMatch, lca: childLCA };
    return { matchCount: res.matchCount + childMatch, lca: null };
  }, { matchCount: 0, lca: null });

  // 子树已找到LCA，向上传递结果
  if (childResult.lca) return [currentMatch + childResult.matchCount, childResult.lca];
  // 当前节点满足LCA条件，向上返回
  if (currentMatch + childResult.matchCount === 2) {
    return [2, node];
  }
  // 未找到LCA，返回当前子树匹配的目标数量
  return [currentMatch + childResult.matchCount, null];
};

const getMinMaxLCA = graph => {
  if (!graph?.children?.length && !graph?.values?.length) return null;
  const minVal = min(graph);
  const maxVal = max(graph);
  const [_, lcaNode] = findLCA(graph, minVal, maxVal);
  // 若需要返回LCA的values数组，修改为 return lcaNode?.values ?? null
  return lcaNode;
}

// 测试调用
console.log(getMinMaxLCA(tree));

逻辑验证 #

样例树中最小值1.056418140526505落在左子树，最大值98.89823527559626落在右子树，二者的最近公共祖先为根节点，运行代码可验证输出结果正确。

内容的提问来源于stack exchange，提问作者halfdead30