使用递归js查找树状对象（不是二叉树）的最低共同祖先

Question

我需要一些帮助来查找树中两个节点的 Lca。那么任何人都可以解释如何使用递归遍历到某个点并取回结果。我看到了很多例子，但没有一个能真正帮助我。这类问题对我来说真的很新，我从来没有使用递归来遍历树结构。感谢任何帮助！

这就是我的树的样子，这是众多示例之一，因为它是随机生成的，而且我不能使用任何循环或 forEach，只允许使用数组方法。

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)));  
};
  
const distance = graph => {
  if (!graph.children.length && !graph.values.length) return; 
     const minValue = min(graph);
     const maxValue = max(graph);
     const findPath = (graph, key1, key2) => {
  
  if (graph.values.includes(key1) || graph.values.includes(key2)) {
     return graph.values;
 };
   
const arr = [graph.values].concat(graph.children.map(graphNode => {
  return findPath(graphNode, key1, key2);
}));
    
  return arr;
};
  
  const Lca = findPath(graph, minValue, maxValue);
  return Lca;
}

Answer 1

您的 findPath 函数 returns graph.values 作为基本情况，这无助于构建路径。相反，应该收集 children.map 迭代的索引作为路径。

然后，当你同时拥有到最小值的路径和到最大值的路径时，你应该忽略它们共有的前缀，并计算代表两个极端节点之间路径上的边的剩余部分。

这是一个可能的实现：

// the selector argument is a function that here will be either Math.min or Math.max:
function findPath(tree, selector) {
    const bestOf = (a, b) => selector(a[0], b[0]) === a[0] ? a : b;  
    const recur = (node, path) =>
        node.children.reduce((acc, child, i) => 
            bestOf(acc, recur(child, path.concat(i))),
        [selector(...node.values), path]);
    return recur(tree, [])[1];
}

function distanceMinMax(tree) {
    const min = findPath(tree, Math.min),
          max = findPath(tree, Math.max),
          common = min.findIndex((child, depth) => max[depth] != child);
    return min.length + max.length - (common < 0 ? min.length : common) * 2;
}

// Demo tree: the minimum is 1 and maximum is 10. Distance is 3.
const tree = {
    children: [{ 
        children: [{ 
            children: [],
            values: [3]
        }],
        values: [5, 1]
    }, {
        children: [{
            children: [{
                children: [],
                values: [9]
            }],
            values: [10]
        }],
        values: [8, 6]
    }],
    values: [2, 4, 7]
};

console.log(distanceMinMax(tree)); // 3

备注

您写道您... “不能使用任何循环或 forEach，只允许使用数组方法。”

这真的很矛盾，因为：

.forEach() 是数组方法；
您的代码使用 .map()，这与 .forEach();
.map()和.includes()都代表一个循环；
当您的数据结构具有 children 个数组时，使用循环是很自然的，因为任何解决方案都必须访问此类数组的每个条目。

使用递归js查找树状对象（不是二叉树）的最低共同祖先

Find lowest common ancestor of tree like object (not binary tree) using recursion js

javascript

recursion

binary-tree

data-structures

备注