JavaScript下强制路径遍历JSON决策树的优化实现求助

需要优化JavaScript中遍历JSON决策树并强制指定路径的实现：

• 决策树包含200+问题，每个答案带有flag，flag有固定优先级顺序（不可修改）
• 要触发目标flag，路径中所有选择的答案的flag优先级必须≤目标flag，且最终路径的最高优先级flag需等于目标flag
• 当前多层循环方案仅能遍历2层路径，存在遗漏且效率低下，需更高效的深度遍历方式，找到有效路径或判断死路

核心规则明确 #

• 优先级顺序：highest priority flag > second priority flag > medium priority flag > lowest priority flag > no flag（索引越小优先级越高）
• 路径有效性要求：
  1. 路径中每个答案的flag优先级不高于目标flag
  2. 路径终点为END，且路径中所有答案的最高优先级flag等于目标flag

高效实现方案：DFS+记忆化/迭代式DFS #

1. 预处理优先级映射 #

先将flag转换为数值优先级，方便快速比较：

export const flag_priority_order = [
    'highest priority flag',
    'second priority flag',
    'medium priority flag',
    'lowest priority flag',
    'no flag',
];

// 生成flag到优先级数值的映射，数值越小优先级越高
const flagPriorityMap = flag_priority_order.reduce((map, flag, index) => {
  map[flag] = index;
  return map;
}, {});

2. 递归DFS+记忆化（适合中小规模树，代码简洁） #

通过记忆化缓存避免重复处理相同状态（当前问题ID+当前路径最高优先级），大幅提升遍历效率：

function findValidPath(questions, targetFlag) {
  const targetPriority = flagPriorityMap[targetFlag];
  const cache = new Map();
  // 生成缓存键，唯一标识当前状态
  const getCacheKey = (qId, currentMaxPriority) => `${qId}-${currentMaxPriority}`;

  const dfs = (currentQId, currentMaxPriority, path) => {
    const cacheKey = getCacheKey(currentQId, currentMaxPriority);
    if (cache.has(cacheKey)) return cache.get(cacheKey);

    const currentQuestion = questions[currentQId];
    if (!currentQuestion) {
      cache.set(cacheKey, null);
      return null;
    }

    // 遍历当前问题的所有答案
    for (const [answerKey, answer] of Object.entries(currentQuestion.answers)) {
      const answerPriority = flagPriorityMap[answer.flags];
      // 剪枝：跳过优先级高于目标的答案
      if (answerPriority > targetPriority) continue;

      // 更新当前路径的最高优先级
      const newMaxPriority = Math.min(currentMaxPriority, answerPriority);
      const newPath = [...path, { question: currentQId, answer: answerKey }];

      if (answer.next_question === 'END') {
        // 到达终点，验证是否符合目标优先级
        if (newMaxPriority === targetPriority) {
          cache.set(cacheKey, newPath);
          return newPath;
        }
        continue;
      }

      // 递归遍历下一个问题
      const result = dfs(answer.next_question, newMaxPriority, newPath);
      if (result) {
        cache.set(cacheKey, result);
        return result;
      }
    }

    // 所有路径均无效，缓存结果
    cache.set(cacheKey, null);
    return null;
  };

  // 从初始问题（示例为"1"）开始遍历，初始最高优先级设为目标优先级
  return dfs("1", targetPriority, []);
}

3. 迭代式DFS（适合大规模树，避免栈溢出） #

对于200+问题的深层树，递归可能触发调用栈溢出，改用迭代式实现更安全：

function findValidPathIterative(questions, targetFlag) {
  const targetPriority = flagPriorityMap[targetFlag];
  // 栈元素：[当前问题ID, 当前路径最高优先级, 已选路径]
  const stack = [["1", targetPriority, []]];
  // 记录已处理的状态，避免重复遍历
  const visited = new Set();

  while (stack.length > 0) {
    const [currentQId, currentMaxPriority, path] = stack.pop();
    const stateKey = `${currentQId}-${currentMaxPriority}`;
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);

    const currentQuestion = questions[currentQId];
    if (!currentQuestion) continue;

    for (const [answerKey, answer] of Object.entries(currentQuestion.answers)) {
      const answerPriority = flagPriorityMap[answer.flags];
      if (answerPriority > targetPriority) continue;

      const newMaxPriority = Math.min(currentMaxPriority, answerPriority);
      const newPath = [...path, { question: currentQId, answer: answerKey }];

      if (answer.next_question === 'END') {
        if (newMaxPriority === targetPriority) {
          return newPath;
        }
        continue;
      }

      // 将下一个问题压入栈，继续遍历
      stack.push([answer.next_question, newMaxPriority, newPath]);
    }
  }

  // 未找到有效路径，返回null表示死路
  return null;
}

方案优势 #

• 全路径覆盖：DFS会遍历所有可能的路径，不会遗漏深层有效路径
• 高效剪枝：提前跳过优先级不符合要求的答案，减少无效遍历
• 状态缓存：记忆化/已访问集合避免重复处理相同状态，针对200+问题的树能大幅提升效率
• 灵活性：递归式简洁易读，迭代式适合大规模树避免栈溢出

使用示例 #

// 假设你的决策树数据存储在treeData变量中
const targetFlag = 'medium priority flag';
const validPath = findValidPath(treeData.questions, targetFlag);

if (validPath) {
  console.log('找到有效路径：', validPath);
} else {
  console.log('无有效路径，为死路');
}

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