代码之家 › 专栏 › 技术社区 › gaurav5430

基于递归期间更改的值从多个递归中中断

tree recursion javascript

gaurav5430 · 技术社区 · 7 年前

编辑:除了这个问题的其他解决方案,我也很想了解这种递归或递归问题是否有模式,我所使用的技术是否有一个名称(即通过引用传递一个对象,以中断基于对象更改的未来递归)?这种技术在其他情况下有用吗?

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;
}

基本上,我是通过嵌套的注释来查找按其id的注释。

我必须遍历当前注释的所有子级并递归地调用此函数。假设我在当前注释的child1中找到了注释,我不想再递归了,只想中断递归,但循环将继续到下一个同级并递归。

return getCommentById(left) || getCommentById(right)

但是我在实现同样的逻辑时遇到了困难,因为我们需要以某种方式存储每个子调用的结果,并根据这个结果来决定是否找到了值。所以我的解决方案使用了一个辅助变量来表示这个值何时被找到。我发现这需要是一个对象而不是一个变量,这样值的变化在随后从child1到child2的递归调用中可见。如果我在child1递归中使用了一个标志并将其设置为true,这是不可能的,因为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);

0 回复 | 直到 7 年前

lampyridae 7 年前

可以使用基于堆栈的迭代树遍历方法。基本思路如下:

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;
}

Nina Scholz 7 年前

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);

gaurav5430 7 年前

为了完整起见添加此项。基于对我试图解决的问题的更好理解,我可以将代码简化为:

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 发现我刚回来 节点

这种方法的灵感来源于: n-ary tree searching function