최대 호출 스택 크기를 초과했습니다. 논리가 잘못된 부분을 파악할 수 없습니다.

Question

아래의 방법을 구현하는 방법을 파악하는 데 문제가 있습니다. 깊이 우선 검색을 사용하여 트리에 값이 있는지 확인하려고하지만 구현에서 무엇이 잘못되었는지는 확실하지 않습니다. 나는이 작업을 수행 할 때

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

이 줄 : contains 부울을 반환해야합니다, 그것은 트리가 부울 값이 포함 된 경우 다시 확인하는 의미가 없기 때문에

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

는 의문이다. 또한 문제는 다음과 같습니다. contains을 동일한 인수 (인수로 this 포함)로 호출하고 있습니다. 즉, "최대 호출 스택 크기 초과"오류 (스택 오버 플로우라고도 함)가 발생하지 않을 것임을 의미합니다. .

대신에, 당신이 그것을 변경해야합니다 :

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

그런 식으로,이 값을 찾아 처음으로, 그것은 반환합니다. 재귀는 기본 사례가이므로 this.children의 값을 찾거나 루프의 끝에서 벗어나기 때문에 예상대로 작동합니다.