写在前面
此系列来源于开源项目：前端 100 问：能搞懂 80%的请把简历给我
为了备战 2021 春招
每天一题，督促自己
从多方面多角度总结答案，丰富知识
已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
简书整合地址：前端 100 问
正文回答
问题
const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]
回答
- bfs利用队列实现，循环中做的是push => shift => push => shift
- dfs利用栈实现，循环中做的是push => pop => push => pop
function bfs(target, id) {
const quene = [...target]
do {
const current = quene.shift()
if (current.children) {
quene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(quene.length)
return undefined
}
function dfs(target, id) {
const stask = [...target]
do {
const current = stask.pop()
if (current.children) {
stask.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(stask.length)
return undefined
}
// 公共的搜索方法，默认bfs
function commonSearch(target, id, mode) {
const staskOrQuene = [...target]
do {
const current = staskOrQuene[mode === 'dfs' ? 'pop' : 'shift']()
if (current.children) {
staskOrQuene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(staskOrQuene.length)
return undefined
}
