寫在前面
此系列來源于開源項(xiàng)目：前端 100 問：能搞懂 80%的請(qǐng)把簡(jiǎn)歷給我
為了備戰(zhàn) 2021 春招
每天一題吼渡，督促自己
從多方面多角度總結(jié)答案蛤肌，豐富知識(shí)
已知數(shù)據(jù)格式业簿，實(shí)現(xiàn)一個(gè)函數(shù) fn 找出鏈條中所有的父級(jí) id
簡(jiǎn)書整合地址：前端 100 問
正文回答
問題
const value = '112'
const fn = (value) => {
...
}
fn(value) // 輸出 [1瘤礁， 11， 112]
回答
- bfs利用隊(duì)列實(shí)現(xiàn)梅尤，循環(huán)中做的是push => shift => push => shift
- dfs利用棧實(shí)現(xiàn)柜思，循環(huán)中做的是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
}
// 公共的搜索方法，默認(rèn)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
}
