业务中常用的递归总结

前言: 上周遇到一个是要对一棵树?进行查询和寻找父节点的需求,首先想到的就是递归

• 但是在写递归之前,一定要搞清楚两点: 入参和返回值,同时一定要有基线条件,即不满足条件的话要结束操作

常用的几种递归方法

1.深度优先遍历

 const tree = (root, id) => {
     if (!root || !root.length)  return

     for (const item of root) {
         if (id === item.id){
             return item
         }
         const find = tree(item.children, id)
         if (find) return find
     }
 }
复制代码

2.广度优先遍历

 const tree = (root, id) => {
     if (!root || !root.length)  return

     for (const item of root) {
         if (id === item.id){
             return item
         }
     }

     const childrens = root.reduce((total, current) => {
         return total.concat(current.children || [])
     },[])

    return tree(childrens, id)
 }

复制代码

3.打平树形结构

// 第一种
const flatten = (tree) => {
    let list = []
    tree.forEach(node => {
        const {children, ...obj} = node
        list.push(obj)
        if (children && children.length){
            const tempList = flatt(children)
            list.push(...tempList)
        }
    })
    return list
}

// 第二种
const flatten = (tree) => {
     return (tree|| [ ]).reduce((total, current) => {
        const {children, ...obj} = current
        return total.concat(obj, flatten(children))
     }, [])
}
复制代码

4.根据id获取父节点

const parentIds = (root, id, parentIdsList = []) => {
    if (!root || !root.length)  return
    for (const node of root) {
        if(node.id === id){
            return parentIdsList
        }
        const find = parentIds(node.children, id, [...parentIdsList, node.id])
        if (find) return find
    }
}

复制代码

5.树形结构 结构处所有人

const flattenUser = (root) => {
    if (!root || !root.length)  return
    const list = []
    root.forEach(node => {
        const { children, type, ...obj } = node
        if (type === 'user'){
            list.push(obj)
        }
        if (children && children.length){
            const tempList = flattenUser(children)
            list.push(...tempList)
        }
    })
    return list
}
复制代码

6.过滤掉所有的用户

const formatTree = (root) => {
    return (root || []).filter(node => node.type === 'admin').map(node => {
        const { children } = node
        return {
            ...node,
            children: formatTree(children)
        }
    })
}
复制代码