js 数组递归过滤算法问题

Question

//源数据
let data = [{
            province: '浙江',
            children: [{
                name: '杭州',
                children: [{
                    name: '下城区',
                    children: [{
                        name: '下城街道',
                        id: '1_1_1',
                    }]
                }, {
                    name: '上城区',
                    id: '1_2',
                }]
            }, {
                name: '宁波',
                id: '2',
            }, {
                name: '温州',
                id: '3',
            }]
        },
        {
            province: '广东',
            children: [{
                name: '广州',
                children: [{
                    name: '越秀区',
                    id: '4_1',
                }, {
                    name: '荔湾区',
                    id: '4_2',
                }]
            }]
        },
    ]
    
    //过滤条件数组
    let filterList = ['1_1_1', '2', '4_1'];
        // 需要考虑 数组节点id不在源数据的情况
        //例如 
        let filterList = ['666', '777'];
    
    
    //最终结果
    [{
            province: '浙江',
            children: [{
                name: '杭州',
                children: [{
                    name: '下城区',
                    children: [{
                        name: '下城街道',
                        id: '1_1_1',
                    }]
                }]
            }, {
                name: '宁波',
                id: '2',
            }]
        },
        {
            province: '广东',
            children: [{
                name: '广州',
                children: [{
                    name: '越秀区',
                    id: '4_1',
                }]
            }]
        },
    ]

数据如上 我想在源数据中获取 id 在过滤数组 filterList中的数据,
如果子节点在filterList 就必须保证对应的父节点完整,
递归层级不固定! 可能存在多级的情况!
求一个高效的算法!请教各位大佬!

Answer 1

再高效的算法反正至少遍历一次，所以递归解决就好了。

写个比较通用的，传入一个函数func用于描述你需要保留的节点,看看够不够简单：

function treeFilter (tree, func) {
  return tree.filter(node => {
    node.children = node.children && treeFilter(node.children, func)
    return func(node) || (node.children && node.children.length)
  })
}

测试：

let result = treeFilter(data, node => filterList.includes(node.id))
console.log(JSON.stringify(result))

输出：

[
    {
        "province":"浙江",
        "children":[
            {
                "name":"杭州",
                "children":[
                    {
                        "name":"下城区",
                        "children":[
                            {
                                "name":"下城街道",
                                "id":"1_1_1"
                            }
                        ]
                    }
                ]
            },
            {
                "name":"宁波",
                "id":"2"
            }
        ]
    },
    {
        "province":"广东",
        "children":[
            {
                "name":"广州",
                "children":[
                    {
                        "name":"越秀区",
                        "id":"4_1"
                    }
                ]
            }
        ]
    }
]

Answer 2

试试这个

function filter(item) {
   if (filterList.indexOf(item.id) > -1) return true;

   if(item.children) filter(item.children);
   
   if(Array.isArray(item.children)) return item.children.some(item => filter(item));
}

data.filter(item => { return filter(item) })

Answer 3

let data = [{
            province: '浙江',
            children: [{
                name: '杭州',
                children: [{
                    name: '下城区',
                    children: [{
                        name: '下城街道',
                        id: '1_1_1',
                    }]
                }, {
                    name: '上城区',
                    id: '1_2',
                }]
            }, {
                name: '宁波',
                id: '2',
            }, {
                name: '温州',
                id: '3',
            }]
        },
        {
            province: '广东',
            children: [{
                name: '广州',
                children: [{
                    name: '越秀区',
                    id: '4_1',
                }, {
                    name: '荔湾区',
                    id: '4_2',
                }]
            }]
        },
    ];
    
function filter (o, keys) {
   if (o.filter) {
       o = o.filter(c => filter(c, keys));
       return o;
   }
   if (o.children) {
       o.children = o.children.filter(c => filter(c, keys));

       if (!o.children.length) {
           delete o.children
       }
   }
   return keys.includes(o.id) || o.children;
}

let result = filter(data, ['1_1_1', '2', '4_1']);

console.log(JSON.stringify(result, null, 4));