разрыв множественной рекурсии на основе значения, которое изменяется во время рекурсии

Question

РЕДАКТИРОВАТЬ: Помимо других решений этой проблемы, я также хотел бы понять, если у такого рода рекурсивных или рекурсивных проблем есть образец, есть ли название технике, которую я использовал (то есть, чтобы передать объект ссылка на разрыв будущей рекурсии на основе изменений объекта)? Полезна ли эта техника в некоторых других сценариях?

Я ищу значение в древовидном дереве, и как только оно найдено, я хочу нарушить рекурсию (есть другие базовые случаи, чтобы сломать пример). Вот как выглядит код:

function getCommentById(root, commentId, foundComment) {
  if (root.id === commentId) {
    return root;
  }

  if (foundComment.comment) {
    return foundComment.comment;
  }

  if (!root.comments) {
    return foundComment.comment;
  } else {
    for (let i = 0; i < root.comments.length; i++) {
      foundComment.comment = getCommentById(
        root.comments[i],
        commentId,
        foundComment
      );
    }
  }

  return foundComment.comment;
}

В основном я просматриваю вложенные комментарии, чтобы найти комментарий по его идентификатору.

Мне нужно перебрать все дочерние элементы текущего комментария и вызвать эту функцию рекурсивно. Допустим, я нашел комментарий в child1 текущего комментария, я хотел бы больше не повторять его и просто выйти из рекурсии, но цикл продолжится до следующего родного брата и повторения. Такого рода вещи были просты в двоичном дереве, так как я мог просто сделать что-то вроде

return getCommentById(left) || getCommentById(right)

но у меня возникли проблемы с реализацией той же логики здесь, потому что нам нужно было бы каким-то образом хранить результат каждого дочернего вызова, и на основании этого решить, нашли ли мы значение или нет. Таким образом, мое решение использует вспомогательную переменную, которая обозначает, когда значение было найдено. Я понял, что это должен быть объект, а не переменная, чтобы изменение значения было видно при последующем вызове рекурсии от child1 к child2. Это было бы невозможно, если бы я только использовал флаг и установил его в true в рекурсии child1, потому что тогда рекурсия child2 все равно увидит флаг как false и продолжит рекурсию.

Есть ли лучший подход? Есть ли название для этого метода использования ссылки на объект для прерывания рекурсии? Как еще это можно реализовать?

РЕДАКТИРОВАТЬ: набор данных для тестирования

const post = {
id: "post1",
title: "Sample Post 1",
description: "This is a sample post",
createdBy: "user1",
createdAt: new Date(),
comments: [
  {
    id: "post1comment1",
    text: "This is comment 1",
    userId: "user1",
    timestamp: new Date().setFullYear(2018),
    comments: [
      {
        id: "post1comment1.1",
        text: "This is sub comment 1 of comment 1",
        userId: "user2",
        timestamp: new Date()
      }
    ]
  },
  {
    id: "post1comment2",
    text: "This is comment 2",
    userId: "user4",
    timestamp: new Date()
  },
  {
    id: "post1comment3",
    text: "This is comment 3",
    userId: "user4",
    timestamp: new Date()
  }
]
  },

использование:

const foundComment = { comment: null };
getCommentById(post, "post1comment1.1", foundComment);

Answer 1

Вы можете получить узел напрямую в качестве результата, не возвращая его обратно через ссылку на объект.

function getCommentById(root, commentId) {
    var temp;

    if (root.id === commentId) return root;
    (root.comments || []).some(node => temp = getCommentById(node, commentId))
    return temp;
}

const
    post = { id: "post1", title: "Sample Post 1", description: "This is a sample post", createdBy: "user1", createdAt: new Date(), comments: [{ id: "post1comment1", text: "This is comment 1", userId: "user1", timestamp: new Date().setFullYear(2018), comments: [{ id: "post1comment1.1", text: "This is sub comment 1 of comment 1", userId: "user2", timestamp: new Date() }] }, { id: "post1comment2", text: "This is comment 2", userId: "user4", timestamp: new Date() }, { id: "post1comment3", text: "This is comment 3", userId: "user4", timestamp: new Date() }] },
    result = getCommentById(post, "post1comment1.1");

console.log(result);

Answer 2

Добавление этого для полноты. Основываясь на лучшем понимании проблемы, которую я пытался решить, я смог сократить свой код до следующего:

function getCommentByIdSimple(root, commentId) {
  if (!root) {
    return null;
  }

  if (root.id === commentId) {
    return root;
  } else {
    let node;
    if (!root.comments) {
      return null;
    }
    for (let i = 0; i < root.comments.length; i++) {
      if ((node = getCommentByIdSimple(root.comments[i], commentId))) {
        return node;
      }
    }
  }

  return null;
}

Проблема, которую я пытался решить, заключалась в том, как выйти из цикла for, как только я нашел нужный комментарий. В приведенной выше реализации я проверяю, найден ли node, я просто возвращаю node, поэтому дальнейшие итерации после возврата игнорируются.

Этот подход был основан на: Функция поиска n-арного дерева

Answer 3

Вы можете использовать итеративный подход к обходу дерева на основе стека.Вот основная идея:

function find_thing(root) {
  var stack = [ root ];
  
  while(0 < stack.length) {
     var current_thing = stack.pop();
     if(is_the_thing(current_thing)) {
       return current_thing;
     }
     
     stack = stack.concat(current_thing.AllMyKids());
  }

  return null;
}