递归遍历具有嵌套属性的整个对象

Question

我有很多技巧(比如在格斗动作中)，我想从中找出所有的序列。每个对象都有一个名为“结果”的属性，该属性包含在此技术之后可以完成的操作。有可能，一个结果包含另一个技术，它包含多个结果本身，这些结果本身可能包含另一个技术，等等。

我目前正在使用递归查找这些序列，如果结果包含一项技术，则函数调用自己，如果结果中没有找到技术，则返回部分序列。

findSequencesRecursively(technique: Technique, partialSequence: Technique[]): Technique[] | null {
    // In order to prevent a stack-overflow, sequences are capped at an arbitrary number,
    // as these are likely infinite cycles as opposed to actual sequences.
    if (partialSequence.length <= 25) {
      for (let result of technique.results) {
        if (result.technique) {
          const completeSequence = this.findSequencesRecursively(
            result.technique,
            [...partialSequence, result.technique]
          );
          if (completeSequence) return completeSequence;
        }
      }
      return partialSequence;
    } else return null;
  }

然而，这总是返回它找到的第一个序列，但不是所有的序列。请考虑以下几点：

在对象t4中，有两个结果包含了一种技术：

{ id: 't4r1', technique: t3, otherInfo: null };
{ id: 't4r4', technique: t2, otherInfo: 'bar' };

(技术t3被命名为后空翻，t1被命名为膝关节动作)

该算法(在其当前状态下总是返回t4 -> t3并查找其结果等)，但由于未找到t4 -> t2的序列，因此无法找到t4 -> t2 -> t1的序列。

如何从这些对象中找到所有序列？

这里有一个StackBlitz重新创建了我的问题，如果您设法解决它，您还应该看到“弯头-打击->蝴蝶-踢->膝盖-动作”作为输出。

Answer 1

你走在正确的道路上，只有很少的细节是错误的。具体来说，你会提前回来，而不去看第二分支和更深的分支。

下面是一个如您所料的示例：

public createSequences(): void {
  function findAllPaths(initialTechniques: Technique[]): SequenceData[] {
    const result: SequenceData[] = [];
    function walk(technique: Technique, currentPath: Technique[] = []): void {
      currentPath = [ ...currentPath, technique ];
      const continuations = technique.results.map(v => v.technique).filter(v => !!v);
      if (continuations.length) {
        continuations.forEach(t => walk(t, currentPath))
      } else {
        result.push({ sequentialTechniques: currentPath });
      }
    }
    initialTechniques.forEach(t => walk(t));
    return result;
  }
  
  this.sequences.push(...findAllPaths(this.data));
}

以及它产生的产出：

Knee-Action
Butterfly-Kick -> Knee-Action
Backflip
Elbow-Strike -> Backflip
Elbow-Strike -> Butterfly-Kick -> Knee-Action

和StackBlitz项目看到它的行动。