写在前面

此系列来源于开源项目：前端 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
}