Поиск пути к целевому объекту во вложенном массиве объектов в Javascript

Question

В настоящее время я работаю над проблемой, которая связана с определением, где мне нужно найти дочерний узел в массиве объектов.Цель может быть на одном или нескольких уровнях глубиной.

Проблема в том, что, как только я нахожу объект, мне также нужно нажать путь, который я выбрал, чтобы добраться до этого объекта, в результирующий массив данных.

В настоящее время я написал код, который может успешно найти дочерний узел:

const buildFullTree = (tree, cat, data = []) => {
  let collection = [tree]

  while (collection.length) {
    let node = collection.shift()

    if (node.id === cat.id) {
      data.push(node)
    }

    collection.unshift(...node.children)
  }

  return data
}

Однако этого недостаточно для получения пути к этому объекту.

IЯ почти уверен, что мне нужно изменить это решение на рекурсивный поиск в глубину, чтобы достичь того, что я ищу, но я не уверен, как изменить цикл while для достижения этой цели.

Answer 1

Если я правильно понимаю ваш вопрос, то, возможно, вы могли бы изменить свою функцию поиска пути следующим образом, чтобы достичь того, что вам нужно:

const buildFullTree = (departmentTree, category, data = []) => {

  const findPath = (node, category) => {

    //If current node matches search node, return tail of path result
    if (node.id === category.id) {
      return [node]

    } else {

      //If current node not search node match, examine children. For first 
      //child that returns an array (path), prepend current node to that 
      //path result
      for (const child of node.children) {
        const childPath = findPath(child, category)
        if (Array.isArray(childPath)) {
          childPath.unshift(child)
          return childPath
        }
      }
    }
  }

  const foundPath = findPath(departmentTree, category)

  // If search from root returns a path, prepend root node to path in
  // data result
  if (Array.isArray(foundPath)) {
    data.push(departmentTree)
    data.push(...foundPath)
  }

  return data
}

const departmentTree = {
  id: 5,
  title: 'department',
  level: 1,
  children: [{
    id: 1,
    parentId: 5,
    title: 'category',
    level: 2,
    children: [{
      id: 15,
      parentId: 1,
      title: 'subcategory',
      level: 3,
      children: []
    }, {
      id: 18,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 26,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 75,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 78,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }, {
    id: 23823,
    title: 'category',
    level: 2,
    children: []
  }, {
    id: 9,
    parentId: 5,
    level: 2,
    title: 'category',
    children: [{
      id: 48414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 2414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 42414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 2323213,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 322332,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }]
};

console.log('Path to 2323213:',
  buildFullTree(departmentTree, {
    id: 2323213
  }).map(node => node.id).join(' -> '))

console.log('Path to 23823:',
  buildFullTree(departmentTree, {
    id: 23823
  }).map(node => node.id).join(' -> '))

console.log('Path to -1 (non existing node):',
  buildFullTree(departmentTree, {
    id: -1
  }).map(node => node.id).join(' -> '))