超出最大调用堆栈大小。想不通哪里逻辑不对

Question

我无法弄清楚如何实施下面的 contains 方法。我正在尝试使用深度优先搜索来查找树是否包含值，但我不确定我的实现有什么问题。

class Tree {
  constructor(val) {
    this.value = val;
    this.children = [];
  }

  addChild(val) {
    this.children.push(new Tree(val));
  }

  contains(val) {
    if (this.value === val) {
      return true;
    } else if (this.children.length > 0) {
      for (var i = 0; i < this.children.length; i++) {
        this.contains(this.children[i].contains(value));
      }
      // When it gets to the leaf node, how do I go back to the previous call? 
      // Do I need to return something here?
    }

    return false; // I may be incorrect on this, but it should return false (execute this line) only when every node has been visited, and there are no more nodes to check. 
  }
};

所以当我这样做时：

const T = new Tree(100);
T.addChild(50);
T.addChild(40);
T.children[0].addChild(3);

console.log(T.contains(40));

由于最大调用堆栈错误，我出错了。

Answer 1

这一行：

this.contains(this.children[i].contains(value));

是有问题的，因为 contains 应该 return 一个布尔值，然后再次检查树是否包含该布尔值是没有意义的。此外，问题出在这一行：您在调用 contains 时使用完全相同的参数（将 this 视为参数），这意味着它永远不会停止，从而导致 "maximum call stack size exceeded"错误 -- a.k.a。堆栈溢出。

相反，您应该将其更改为：

if (this.children[i].contains(value))
    return true;

这样，第一次找到值时，它 returns。递归按预期工作，因为它有一个 基本情况 ，即要么在 this.children 中找到值，要么在循环结束时掉下来。

超出最大调用堆栈大小。想不通哪里逻辑不对

Maximum call stack size exceeded. Can't figure out where logic is incorrect

javascript

tree

recursion

depth-first-search