[알고리즘/자바스크립트] 트리에서 조건에 맞는 값만 필터하기 (Tree Collect) - Breadth-First Search

https://im-developer.tistory.com/152

[알고리즘/자바스크립트] 트리에서 조건에 맞는 값만 필터하기 (Tree Collect) - Depth-First Search

Tree Collect

지난번에 푼 문제와 완벽하게 동일하지만 지난번에는 Depth-First Search로 풀었다면, 오늘은 Breadth-First Search로 풀어야한다.

 

 

 

 

두 가지 방식의 차이점은 이렇다. Depth-firsh search는 자식 요소부터 검사하고 형제 노드들을 검사하는데, Breadth-first search는 형제 노드들을 먼저 검사하고 자식 요소로 내려간다.

 

 

---

 

 

Tree.prototype.BFSelect = function (filter) {
  /* return an array of values for which the function filter(value, depth) returns true
  *
  * TODO: implement me!
  */
  const result = [];

  const collectValue = (node, depth, isChecked) => {
    if (!isChecked && filter(node.value, depth)) {
      result.push(node.value);
    }

    if (node.children.length > 0) {
      if (node.children[1]) {
        if (filter(node.children[0].value, depth + 1)) {
          result.push(node.children[0].value);
        }
        if (filter(node.children[1].value, depth + 1)) {
          result.push(node.children[1].value);
        }
        collectValue(node.children[0], depth + 1, true);
        collectValue(node.children[1], depth + 1, true);
      } else {
        collectValue(node.children[0], depth + 1);
      }
    }

    return result;
  }

  return collectValue(this, 0);
};

 

일단 어떻게 풀어야할지 잘 감이 안잡혀서

노가다로 왼쪽 노드, 오른쪽 노드를 써가면서 풀어보았다.

 

 

Tree.prototype.BFSelect = function (filter) {
  /* return an array of values for which the function filter(value, depth) returns true
  *
  * TODO: implement me!
  */
  const result = [];

  const collectValue = (node, depth, isChecked) => {
    if (!isChecked && filter(node.value, depth)) {
      result.push(node.value);
    }

    if (node.children.length > 0) {
      for (let i = 0; i < node.children.length; i++) {
        if (filter(node.children[i].value, depth + 1)) {
          result.push(node.children[i].value);
        }
      }
      for (let i = 0; i < node.children.length; i++) {
        collectValue(node.children[i], depth + 1, true);
      }
    }

    return result;
  }

  return collectValue(this, 0);
};

 

위 코드가 테스트 통과하고 난 뒤 다시 간소화시켜보았다.

Breadth-First Search는 형제 노드부터 모두 검사를 하고 하위로 넘어가야하므로

for문으로 형제 노드의 검사를 모두 끝낸 후에 아래로 내려가는 재귀 호출을 한다.