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

Tree Collect

Implement a `collect` method on this binary Tree class.

Collect accepts a filter function, calls that function on each of the nodes in turn, and returns a flat array of node values of the tree for which the filter returns true.

 

 

Example:

var root1 = new Tree(1);
var branch2 = root1.addChild(2);
var branch3 = root1.addChild(3);
var leaf4 = branch2.addChild(4);
var leaf5 = branch2.addChild(5);
var leaf6 = branch3.addChild(6);
var leaf7 = branch3.addChild(7);

root1.collect(function (value, depth) { 
  return value % 2;
}); // [1, 5, 3, 7]

root1.collect(function (value, depth) {
  return depth === 1;
}); // [2, 3]

 

binary tree에서 값을 filter할 조건을 리턴하는 함수를 인자로 주면

그 조건에 맞는 값만 배열로 출력하는 문제이다.

 

필터 함수의 인자에는 value와 depth가 인자로 들어가는데,

value는 트리 노드의 value값이고, depth는 노드의 레벨 depth를 말한다.

 

var Tree = function (value) {
  this.value = value;
  this.children = [];
};

Tree.prototype.collect = function (filter) {
  // 여기를 채워보세요!
};

 

---

 

Tree.prototype.collect = function (filter) {
  const result = [];

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

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

    return result;
  }

  return collectValue(this, 0);
};

 

 

푸는데 정말 정말 정말 고생했던 문제였다...ㅠㅠ

value를 걸러내는것은 괜찮았는데 문제는 depth를 찾아내는 것이었다.

 

재귀로 풀 때, 무조건 깊이를 우선해서 탐색하기 때문에

depth를 그냥 변수를 줘서 더하는 걸로는 풀 수가 없어서

몇 시간을 삽질을 했다.

 

depth 구하는 함수를 따로 만들어서 따로 로직을 짜다가 계속 무한 루프에 빠지고...

그렇게 열심히 땅굴을 팔다가 depth++를 할게 아니고

for문 안에서 depth + 1을 하면 각 노드에 맞는 level을 구할 수 있다는 사실을 깨달았다...

ㅜㅜ....

 

 

그니까 depth로 건내주는 인자의 초기값은 무조건 0이고,

만약에 초기 노드의 children이 없다면 노드 하나만 검사하고 종료한다.

 

 

만약에 노드에 children이 있다면 children을 검사하기 시작하는데

depth는 depth++이 아니고 depth+1을 한다(!!!!)

그러면 만약에 depth가 0인 노드의 자식들은 무조건 재귀를 탈 때,

depth+1 = 1로 depth가 잡힌다.

만약에 depth가 1인 노드들이 자식이 있어서 다시 재귀를 탄다면 

이번에는 depth+1이 2가 되기 때문에 2를 넣어서 재귀를 탄다.

 

이렇게 간단한 것을... 거의 다 풀어놓고 depth++을 해버려서 못 풀다니...ㅠㅠ

그래도 덕분에 이 문제를 잊어버리진 않을 것 같다.