JavaScript: Найти всех родителей для элемента в дереве рекурсивный

Question

У меня есть что-то вроде этого дерева

var datas = {
    'tree': [
        {
            'name': 'name1',
            'tree': [
                {'name': 'name2'},
                {'name': 'name3'},
                {
                    'name': 'name4',
                    'tree': [
                        {'name': 'name5'},
                        {'name': 'name6'}
                    ]
                },
                {'name': 'name7'}
            ]
        },
        {
            'name': 'name8',
            'tree': [
                {'name': 'name9'}
            ]
        }
    ]
}

Я хочу найти всех родителей указанного идентификатора

, например, в демонстрации дерева, если я ищу 'name5'Я хочу найти "name1, name4, name5"

Я написал этот код, но результаты неверны, и я получил идентификаторы других элементов, а не только родителей

Это мой код

 keys: string[];
  pathFound: boolean = false;
 getLevel(event: iEventBase, id: string, path: string[]): void {
    if (this.pathFound) return;
    event.content.forEach((key) => {
      if (key.id == id) {
        if(!path){
          path =  [];;
        }
        path.push(key.id);
        this.keys = path;
        this.pathFound = true;
        return;
      }
      if (key.type === "page") {
        if(!path){
          path = [];
        }
        path.push(key.id);
        this.getLevel(key, id, path);
      }
    })
  }
}
this.getLevel(state.mainEvent.content.page, event.id, null);

Answer 1

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

function find(array, name) {
    var result;
    array.some(o => {
        var temp;
        if (o.name === name) {
            return result = [name];
        }
        temp = find(o.tree || [], name);
        if (temp) {
            return result = [o.name, ...temp];
        }
    });
    return result;
}

var datas = { tree: [{ name: 'name1', tree: [{ name: 'name2' }, { name: 'name3' }, { name: 'name4', tree: [{ name: 'name5' }, { name: 'name6' }] }, { name: 'name7' }] }, { name: 'name8', tree: [{ name: 'name9' }] }] };

console.log(find(datas.tree, 'name5'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Возможно, вы могли бы принять рекурсивный подход к этой проблеме. Основная идея здесь состоит в том, чтобы посмотреть вниз по дереву на узел, имя которого совпадает с именем узла, для которого вы ищете родителей (например, name5).

Как только такой узел будет найден, возвращайте массив, добавляя соответствующее родительское имя узла в массив, пока рекурсия полностью не раскрутится.

Итак, что-то вроде этого должно работать:

var datas = {
    'tree': [
        {
            'name': 'name1',
            'tree': [
                {'name': 'name2'},
                {'name': 'name3'},
                {
                    'name': 'name4',
                    'tree': [
                        {'name': 'name5'},
                        {'name': 'name6'}
                    ]
                },
                {'name': 'name7'}
            ]
        },
        {
            'name': 'name8',
            'tree': [
                {'name': 'name9'}
            ]
        }
    ]
}

function findParents(node, searchForName) {

  // If current node name matches the search name, return
  // empty array which is the beginning of our parent result
  if(node.name === searchForName) {
    return []
  }
  
  // Otherwise, if this node has a tree field/value, recursively
  // process the nodes in this tree array
  if(Array.isArray(node.tree)) {
  
    for(var treeNode of node.tree) {

      // Recursively process treeNode. If an array result is
      // returned, then add the treeNode.name to that result
      // and return recursively
      const childResult = findParents(treeNode, searchForName)

      if(Array.isArray(childResult)) {
        return [ treeNode.name ].concat( childResult );
      }
    }
  }
}

console.log( findParents(datas, 'name5') )