前端算法题求解，获取下一个id

Question

// 请问如何实现函数 getNextActiveId 这个函数

const list = [
    {
        id: "A",
        detail: [
            {
                id: "A_a",
            },
            {
                id: "A_b",
            },
        ],
    },
    {
        id: "B",
        detail: [
            {
                id: "B_a",
            },
        ],
    },
    {
        id: "C",
        detail: [],
    },
];

// 初始值,list第一个索引
let activeId = "0";


function getNextActiveId(activeId){
}


console.log(getNextActiveId(activeId)); // 第一次执行，返回 '0_0'
activeId=getNextActiveId(activeId);

console.log(getNextActiveId(activeId)); // 第二次执行，返回 '0_1'
activeId=getNextActiveId(activeId);

console.log(getNextActiveId(activeId)); // 第三次执行，返回 '1'
activeId=getNextActiveId(activeId);

console.log(getNextActiveId(activeId)); // 第四次执行，返回 '1_0'
activeId=getNextActiveId(activeId);

console.log(getNextActiveId(activeId)); // 第五次执行，返回 '2'
activeId=getNextActiveId(activeId);

Answer 1

从结果来看，是树形的深度递归，需要使用递归函数，具体过程看代码中的注释。建议阅读：使用递归遍历并转换树形数据（以 TypeScript 为例）

function getNextActiveId(activeId) {
    // 拿到序号列表
    const indexes = activeId.split("_");
    return (goThrough(list) ?? []).join("_");

    // 定义递归方法，深度递归查找，返回的是已经找到的路径（数组表示）
    function goThrough(nodes, serial = 0) {
        // 由于 nodes 无效或为空的情况，无论如何都不可能在这个节点上找到值，
        // 所以提前判断，直接返回表示未找到值的 undefined,
        // 表示应该在递归的上一层去取值。
        if (!nodes?.length) {
            return;
        }

        // 如果 serial 已经超过了 indexes 的长度，说明找完了给出的序列，
        // 此时如果 nodes 有值，说明它是 indexes 序列指示的最后一个节点的子节点，
        // 那么，如果 nodes 有效且非空（无效过空的情况前面已经过滤了），
        // 应该返回[0]，即包含最后一个节点的路径，
        // 祖先路径会在递归返回的时候逐渐补充；
        if (serial >= indexes.length) {
            return [0];
        }

        // serial 所示序号在 indexes 长度范围内，
        // 需要把这个节点找出来：先从 indexes 中拿到对应的序号，再从 nodes 中拿到节点
        const index = ~~indexes[serial];
        const node = nodes[index];

        // 对这个节点进行递归查找，拿到返回的子路径部分。
        // 如果 nextIds 为 undefined，表示没找到有效子路径（具体情况见上面说明）
        // 如果 nextIds 有效一定是个表示找到的子路径数组，
        // 这个子路径是需要得到的下一个 id 的子路径（逻辑除了上面的 return [0]，还有下面的部分
        const nextIds = goThrough(node?.detail, serial + 1);

        if (nextIds) { return [index, ...nextIds]; }

        // 未找到子路径的情况，先判断当前 nodes 是否有下一个节点
        // 如果有，直接返回下一个节点的序号，
        // 如果没有，返回 undefined 回退给递归的上一层去解决
        if (index + 1 < nodes.length) {
            return [index + 1];
        }
        return;
    }
}


// 从 "0" 开始依次取出下一个，直到返回 ""（就是没找到，或者说找完了）
for (let activeId = "0"; activeId;) {
    activeId = getNextActiveId(activeId);
    console.log(activeId);
}

输出

0_0
0_1
1
1_0
2

Answer 2

function getNextActiveId(activeId) {
    process: {
        var id = activeId.split("_");
        var cache = [list];
        find: for (var i = 0; i < id.length; ++i) {
            var item = cache[cache.length - 1][id[i]];
            if (!item || !item.id) break process;
            if (item.detail && item.detail.length) {
                cache.push(item.detail);
            }
        }
        traverse: for (var i = cache.length; i--;) {
            if (i >= id.length) {
                activeId += "_0";
                break process;
            }
            var item = cache[i][++id[i]];
            if (item && item.id) {
                return id.slice(0, i + 1).join("_");
            }
        }
    }
    return activeId;
}
for (var id = "0", activeId; id !== activeId;) {
    console.dir(id = getNextActiveId(activeId = id));
}