请求编写递归函数实现问答树的全路径生成

问题描述 #

现有一个问答树结构数据，每个问题包含questionIdx和选项数组；选项内有answerLabel和可选的linksTo字段，linksTo指定下一个问题的索引，若无linksTo则该路径结束。需要遍历数据生成所有可能的路径。

示例输入数据 #

const mockData: Tree = {
  name: "My tree",
  description: "string",
  questions: [
    {
      questionIdx: 1,
      question: "Do you like potato",
      description: "string",
      options: [
        {
          answerIdx: 1,
          answerLabel: "Yes",
          linksTo: 2,
        },
        {
          answerIdx: 2,
          answerLabel: "No",
          linksTo: 3,
        },
      ],
    },
    {
      questionIdx: 2,
      question: "Do you like carrot",
      description: "string",
      options: [
        {
          answerIdx: 1,
          answerLabel: "Yes",
          linksTo: 3,
        },
        {
          answerIdx: 2,
          answerLabel: "No",
        },
      ],
    },
    {
      questionIdx: 3,
      question: "Do you like anything",
      description: "string",
      options: [
        {
          answerIdx: 1,
          answerLabel: "Yes",
        },
        {
          answerIdx: 2,
          answerLabel: "No",
        },
      ],
    },
  ],
};

预期输出格式 #

const mockedOutput: PathsData = {
  name: "My tree",
  paths: [
    {
      pathIdx: 1,
      show: true,
      path: [
        {
          questionIdx: 1,
          question: "Do you like potato",
          answerLabel: "Yes",
          linksTo: 2,
        },
        {
          questionIdx: 2,
          question: "Do you like carrot",
          answerLabel: "Yes",
          linksTo: 3,
        },
        {
          questionIdx: 3,
          question: "Do you like anything",
          answerLabel: "Yes",
        },
      ],
    },
    {
      pathIdx: 2,
      show: true,
      path: [
        {
          questionIdx: 1,
          question: "Do you like potato",
          answerLabel: "Yes",
          linksTo: 2,
        },
        {
          questionIdx: 2,
          question: "Do you like carrot",
          answerLabel: "Yes",
          linksTo: 3,
        },
        {
          questionIdx: 3,
          question: "Do you like anything",
          answerLabel: "No",
        },
      ],
    },
    {
      pathIdx: 3,
      show: true,
      path: [
        {
          questionIdx: 1,
          question: "Do you like potato",
          answerLabel: "No",
          linksTo: 3,
        },
        {
          questionIdx: 3,
          question: "Do you like anything",
          answerLabel: "Yes",
        },
      ],
    },
    {
      pathIdx: 4,
      show: true,
      path: [
        {
          questionIdx: 1,
          question: "Do you like potato",
          answerLabel: "No",
          linksTo: 3,
        },
        {
          questionIdx: 3,
          question: "Do you like anything",
          answerLabel: "No",
        },
      ],
    },
    {
      pathIdx: 5,
      show: true,
      path: [
        {
          questionIdx: 1,
          question: "Do you like potato",
          answerLabel: "Yes",
          linksTo: 2,
        },
        {
          questionIdx: 2,
          question: "Do you like carrot",
          answerLabel: "No",
        },
      ],
    },
  ],
};

解决方案 #

核心思路是用递归函数遍历每个选项的分支：

1. 先将问题数组转换成以questionIdx为键的映射，方便快速查找下一个问题
2. 递归函数接收当前路径和当前问题索引，遍历当前问题的所有选项：
   • 对每个选项，生成新的路径节点（包含问题索引、问题文本、选项标签、linksTo）
   • 如果选项有linksTo，则继续递归处理下一个问题
   • 如果没有linksTo，则当前路径完成，添加到结果列表

类型定义 #

首先补充必要的TypeScript类型：

// 选项类型
interface AnswerOption {
  answerIdx: number;
  answerLabel: string;
  linksTo?: number;
}

// 问题类型
interface Question {
  questionIdx: number;
  question: string;
  description: string;
  options: AnswerOption[];
}

// 输入的树结构类型
interface Tree {
  name: string;
  description: string;
  questions: Question[];
}

// 路径中的节点类型
interface PathNode {
  questionIdx: number;
  question: string;
  answerLabel: string;
  linksTo?: number;
}

// 单个路径类型
interface PathItem {
  pathIdx: number;
  show: boolean;
  path: PathNode[];
}

// 输出的路径数据类型
interface PathsData {
  name: string;
  paths: PathItem[];
}

递归实现函数 #

function generateAllPaths(tree: Tree): PathsData {
  // 将问题数组转换为索引映射，方便快速查找
  const questionMap = new Map<number, Question>();
  tree.questions.forEach(q => questionMap.set(q.questionIdx, q));

  const allPaths: PathNode[][] = [];

  // 递归函数：生成从当前问题开始的所有路径
  function traverse(currentQuestionIdx: number, currentPath: PathNode[]) {
    const currentQuestion = questionMap.get(currentQuestionIdx);
    if (!currentQuestion) return;

    // 遍历当前问题的每个选项
    for (const option of currentQuestion.options) {
      // 创建当前选项对应的路径节点
      const pathNode: PathNode = {
        questionIdx: currentQuestion.questionIdx,
        question: currentQuestion.question,
        answerLabel: option.answerLabel,
        linksTo: option.linksTo
      };

      // 生成新路径
      const newPath = [...currentPath, pathNode];

      if (option.linksTo) {
        // 如果有下一个问题，继续递归
        traverse(option.linksTo, newPath);
      } else {
        // 没有下一个问题，路径完成，加入结果
        allPaths.push(newPath);
      }
    }
  }

  // 从第一个问题开始遍历（假设questionIdx=1是起始点）
  traverse(1, []);

  // 转换为预期的输出格式
  return {
    name: tree.name,
    paths: allPaths.map((path, index) => ({
      pathIdx: index + 1,
      show: true,
      path
    }))
  };
}

调用示例 #

// 生成路径
const result = generateAllPaths(mockData);
console.log(result);

该函数会正确遍历所有分支，生成符合要求的完整路径集合。

内容的提问来源于stack exchange，提问作者Jacki