DFS输出所有匹配的元素及其祖先: javascript

Question

给定的

//  tree data structure
Elephant --> Duck
         --> Hamster -->  Elephant1
                     -->  Elephant2

Hamster --> Elephant --> Fish
        --> Dog -------> Elephant

Dog --> Unicorn
    --> Fish --> Hamster
             --> Elephant --> Elephant

当用户键入术语“Ele”时，希望输出结果，以便将所有树简化为以下格式(该格式具有与其祖先匹配的结果)

Elephant --> Hamster -->  Elephant1
                     -->  Elephant2  
Hamster --> Elephant 
        --> Dog -------> Elephant
Dog --> Fish  --> Elephant --> Elephant

给定的

this.tree = [
    { id:1, name: 'Elephant',children:[ 
          { id:2, name: 'Duck' },
          { id:3, name: 'Hamster', children: [
                   { id: 4, name: 'Elephant1', id: 5, name: 'Elephant2' }]
          }
    ]},
    { id:5A, name: 'Hamster', children: [
          { id:6, name: 'Elephant', children: [
                  { id:7, name: 'Fish' }
          ]},
          { id:8, name: 'Dog', children: [
                  { id:9, name: 'Elephant' }
          ]}
    ]},
    { id:10, name: 'Dog', children: [
          { id:11, name: 'Unicorn' },
          { id:12, name: 'Fish', children: [
                  { id:13, name: 'Hamster' },
                  { id:14, name: 'Elephant', children: 
                         [{ id:15, name: 'Elephant' }
                  ]},
          ]}
    ]},
    { id:16, name: 'Elephant', children: [
          { id:17, name: 'Duck' }, 
          { id:18, name: 'Hamster', children: [
                 { id:19, name: 'Elephant' }, 
                 { id:20, name: 'Fish' }
          ]}
    ]}
]

我的尝试：

我尝试了以下使用深度优先搜索遍历，但有问题，包括它的祖先，当它的子项有匹配项。目前，该代码只输出子程序的匹配结果，而不输出其祖先。我已经完成了一半的解决方案(可能需要稍微修改一下我的尝试解决方案)，但在回溯过程中遇到了困难。一直在搜索DFS的资源，如果有人知道这一点，我将不胜感激。

onSearch(term) {
    let found = this.search(term, JSON.parse(JSON.stringify(this.tree)));
    console.log(found);
}

search(term, parent, path, basket) {
    let fork = path.slice(0);

    let found, { name, id, children } = parent;
    let nameId = name + ':' +id;

    fork.push(nameId);
    if (name.toLowerCase().indexOf(term) !== -1) {
        basket.push(fork);
        fork = [];
        return basket
    } 
    if (!!children && children.length > 0) {
        for (let child of parent.children) {
            this.search(term, child, fork, basket)  
        }
        return basket;
    } 

    if (children.length === 0) {
        return [];
    }
  }

this.onSearch('elep');

然而，上述尝试解决方案返回以下结果，这是不完全正确的。

Elephant  --> Hamster -->  Elephant1 

Hamster --> Elephant  
        --> Dog -------> Elephant

Dog  --> Fish  --> Elephant  

渴望的解决方案是输出

Elephant --> Hamster -->  Elephant1
                     -->  Elephant2  
Hamster --> Elephant 
        --> Dog -------> Elephant
Dog --> Fish  --> Elephant --> Elephant

Answer 1

经过几次尝试，找到了下面的解决方案，它将输出所需的解决方案

onSearch(term) {
   let found = this.search(term, JSON.parse(JSON.stringify(this.tree)));
   console.log(found);
}
search(term, parent, path, basket) {
    let found, { name, id, children } = parent;
    let nameId = name + ':' +id;

    let fork = path.slice(0);
    fork.push(nameId);

    if (name.toLowerCase().indexOf(term) !== -1) {
        basket.push([fork]);
    } 
    if (!!children && children.length > 0) {
        for (let child of parent.children) {
            this.search(term, child, fork, basket)
        }
        return basket;
    } 
}