如何优雅查找深度嵌套评论对象？已有递归实现求优化

问题描述 #

我们拥有一个深度嵌套的评论数组，需要查找其中id为131的深层评论。已实现一段递归查找函数（可正常返回目标对象），想请教是否存在更优雅的实现方式？已知可以先扁平化数组再查找，但希望有更优方案（注：所有评论id唯一）。

嵌套评论数组 #

const comments = [
  {
    id: 1,
    text: "Comment 1",
    comments: [
      {
        id: 11,
        text: "Comment 1a",
        comments: [
          { id: 111, text: "Comment 11a", comments: [] },
          { id: 112, text: "Comment 11b", comments: [] },
          { id: 113, text: "Comment 11c", comments: [] },
        ],
      },
      {
        id: 12,
        text: "Comment 12",
        comments: [
          { id: 121, text: "Comment 12a", comments: [] },
          { id: 122, text: "Comment 12b", comments: [] },
          { id: 123, text: "Comment 12c", comments: [] },
        ],
      },
      {
        id: 13,
        text: "Comment 1c",
        comments: [
          { id: 124, text: "Comment 13a", comments: [] },
          { id: 125, text: "Comment 13b", comments: [] },
          { id: 126, text: "Comment 13c", comments: [] },
        ],
      },
    ],
  },
  {
    id: 2,
    text: "Comment 2",
    comments: [
      {
        id: 21,
        text: "Comment 2a",
        comments: [
          { id: 127, text: "Comment 21a", comments: [] },
          { id: 128, text: "Comment 21b", comments: [] },
          {
            id: 129,
            text: "Comment 21c",
            comments: [
              {
                id: 130,
                text: "Comment 21cc",
                comments: [
                  { id: 131, text: "Comment 21ccc", comments: [] },
                ],
              },
            ],
          },
        ],
      },
      {
        id: 22,
        text: "Comment 2b",
        comments: [
          { id: 135, text: "Comment 21a", comments: [] },
          { id: 132, text: "Comment 21b", comments: [] },
          { id: 133, text: "Comment 21c", comments: [] },
        ],
      },
      { id: 23, text: "Comment 2c", comments: [] },
    ],
  },
  {
    id: 3,
    text: "Comment 3",
    comments: [
      { id: 31, text: "Comment 3a", comments: [] },
      { id: 32, text: "Comment 3b", comments: [] },
      { id: 33, text: "Comment 3c", comments: [] },
    ],
  },
];

原递归实现 #

function recursiveFind(comments, commentId) {
  const result = [];
  function loop(comments, commentId, result) {
    for (const comment of comments) {
      if (comment.id === commentId) {
        result.push(comment);
      }
      if (result.length <= 0 && comment.comments) {
        loop(comment.comments, commentId, result);
      }
    }
  }
  loop(comments, commentId, result);
  return result.length > 0 ? result[0] : false;
}
const found = recursiveFind(comments, 131);
console.log(found);//returns object

优化方案 #

1. 精简递归实现（找到即终止） #

原递归用数组存储结果，可改为直接返回找到的对象，一旦找到就终止后续递归和遍历，效率更高：

function findCommentById(comments, targetId) {
  for (const comment of comments) {
    if (comment.id === targetId) {
      return comment;
    }
    // 递归查找子评论，找到就返回
    const found = findCommentById(comment.comments, targetId);
    if (found) return found;
  }
  // 没找到返回null
  return null;
}

这个版本逻辑更直接，无需额外的结果数组，找到目标后立即回溯终止，避免不必要的遍历。

2. 迭代式深度优先搜索（DFS） #

如果评论嵌套层级极深，递归可能导致栈溢出，用栈实现迭代式DFS更安全：

function findCommentByIdDFS(comments, targetId) {
  const stack = [...comments];
  while (stack.length > 0) {
    const current = stack.pop();
    if (current.id === targetId) {
      return current;
    }
    // 子评论反转后压入栈，保持原遍历顺序
    stack.push(...current.comments.reverse());
  }
  return null;
}

3. 迭代式广度优先搜索（BFS） #

如果目标评论大概率在浅层，BFS会更快找到结果：

function findCommentByIdBFS(comments, targetId) {
  const queue = [...comments];
  while (queue.length > 0) {
    const current = queue.shift();
    if (current.id === targetId) {
      return current;
    }
    queue.push(...current.comments);
  }
  return null;
}

4. 预处理映射（适合多次查找） #

如果需要频繁根据id查找评论，建议先遍历一次所有评论，构建id到评论对象的映射，后续查找直接O(1)时间：

// 预处理构建映射
const commentMap = new Map();
function buildCommentMap(comments) {
  for (const comment of comments) {
    commentMap.set(comment.id, comment);
    buildCommentMap(comment.comments);
  }
}
buildCommentMap(comments);

// 后续查找直接用map.get
const foundComment = commentMap.get(131);

这种方案适合多次查找的场景，预处理一次后，每次查找都是常数时间，非常高效。

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