第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id

[DreamLee1997]

法一：

• 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
}

法二：

let list = [{
    id: '1',
    children: [{
        id: '11',
        children: [{
            id: '111'
        }, {
            id: '112'
        }]
    }]
}];

function fn(value) {
    // 回溯的标记
    let _p = Symbol('parent');
    // 找到子节点
    let result;
    function _fn(arr, p) {
        for (let i = 0; i < arr.length; i++) {
            arr[i][_p] = p;
            if (arr[i].id === value) {
                result = arr[i];
                return;
            }
            !result && arr[i].children && _fn(arr[i].children, arr[i])
        }
        if (result) return;
    }
    _fn(list, null);
    let tmp = [];
    if (!result) return null;
    while (result) {
        tmp.unshift(result.id);
        result = result[_p];
    }
    return tmp;
}

• 思路是找到子节点，再回溯找父节点
• 复杂度是O(n)，循环n次子节点，但是需要额外空间记录父节点引用