使用递归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函数返回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数组时，使用循环是很自然的，因为任何解决方案都必须访问这样一个数组的每个条目。