如何用JavaScript递归查找菜单的叶子节点？

原代码存在的问题 #

1. 逻辑判断错位：代码在reduce里遍历所有菜单节点，但判断的是传入的id有没有子节点，而非先找到id的子节点再处理，完全搞反了遍历对象
2. 递归结果未合并：调用getChildren(array, menuId)时，没有把递归返回的叶子节点数组合并到结果r里，等于白调用
3. 叶子节点判断时机错误：应该判断当前节点是否有子节点，而非判断传入的父节点有没有子节点

修正后的递归实现 #

function getLeafNodes(menuList, parentId) {
    // 先找到当前父节点的所有直接子节点
    const children = menuList.filter(item => item.parentId === parentId);
    
    let leafNodes = [];
    for (const child of children) {
        // 判断当前子节点是否是叶子节点：没有任何子节点以它为parentId
        const hasChildren = menuList.some(item => item.parentId === child.menuId);
        if (!hasChildren) {
            leafNodes.push(child.menuId);
        } else {
            // 递归查找子节点的叶子节点，并合并结果
            leafNodes = leafNodes.concat(getLeafNodes(menuList, child.menuId));
        }
    }
    return leafNodes;
}

测试验证 #

用给定的菜单数据调用：

const menuData = [
    {"menuId":"1001","depth":"1","parentId":"0"},
    {"menuId":"1002","depth":"1","parentId":"0"},
    {"menuId":"1003","depth":"2","parentId":"1001"},
    {"menuId":"1004","depth":"2","parentId":"1001"},
    {"menuId":"1005","depth":"3","parentId":"1003"}, 
    {"menuId":"1006","depth":"3","parentId":"1004"}, 
    {"menuId":"1007","depth":"4","parentId":"1006"}, 
    {"menuId":"1008","depth":"4","parentId":"1006"}, 
    {"menuId":"1009","depth":"5","parentId":"1008"},
];

console.log(getLeafNodes(menuData, "1001")); // 输出 ["1005", "1007", "1009"]
console.log(getLeafNodes(menuData, "1004")); // 输出 ["1007", "1009"]

优化建议（提升性能） #

如果菜单数据量较大，每次filter和some都会遍历整个数组，效率较低。可以先构建一个父ID到子节点列表的映射表，减少重复遍历：

// 先构建映射表，只需要执行一次
function buildMenuMap(menuList) {
    const map = {};
    menuList.forEach(item => {
        if (!map[item.parentId]) {
            map[item.parentId] = [];
        }
        map[item.parentId].push(item);
    });
    return map;
}

// 基于映射表的递归函数
function getLeafNodesWithMap(menuMap, parentId) {
    const children = menuMap[parentId] || [];
    let leafNodes = [];
    
    for (const child of children) {
        // 通过映射表判断是否有子节点
        const hasChildren = !!menuMap[child.menuId];
        if (!hasChildren) {
            leafNodes.push(child.menuId);
        } else {
            leafNodes = leafNodes.concat(getLeafNodesWithMap(menuMap, child.menuId));
        }
    }
    return leafNodes;
}

// 使用方式
const menuMap = buildMenuMap(menuData);
console.log(getLeafNodesWithMap(menuMap, "1001")); // 同样输出正确结果

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