DFS tree

문제

문제설명

임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.

입출력 예시

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]

---

문제 해결

let dfs = function (node) {
  let arr = [];
  function repeat(innerNode) {
    arr.push(innerNode.value);

    if (innerNode.children) {
      for (let i = 0; i < innerNode.children.length; i++) {
        repeat(innerNode.children[i]);
      }
    }
  }
  repeat(node);
  return arr;
};

let Node = function (value) {
  this.value = value;
  this.children = [];
};

Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

위 코드에서 재귀함수를 사용하였는데, arr가 초기화되어 원하는 값을 얻을 수 없었다. 그래서 내부함수를 만들어주었고, 해당 내부함수를 재귀 호출하는 방법으로 arr가 초기화되지 않도록 하였다.

하지만 이렇게 되면 굳이 내부함수를 생성해야 하는 번거로움이 있다.

dfs를 재귀호출하면서 arr는 초기화되지 않는, 이전의 함수 실행의 결과값을 반영하는 코드가 필요해 보인다.
해당 코드는 아래와 같다.

let dfs = function (node) {
  let values = [node.value];

  node.children.forEach((n) => {
    values = values.concat(dfs(n));
  });

  return values;
};

array 메소드 concat을 사용하는 것이다.
values에 첫번째 value를 할당하고 이후 concat으로 생성된 배열을 재할당하는 것이다.