使用遞回js查找樹狀物件（不是二叉樹）的最低共同祖先

我需要一些幫助來查找樹中兩個節點的 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;
}

uj5u.com熱心網友回復：

您的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陣列時，使用回圈是很自然的，因為任何解決方案都必須訪問此類陣列的每個條目。

標籤：javascript 递归 数据结构 二叉树

上一篇：我在遞回函式中沒有得到任何輸出

下一篇：從動態嵌套陣列生成物件的平面陣列