Algorithm problem-07

1. 문제

• tree를 작성하는 함수에서 임의로 작성된 tree를 DFS하는 함수를 작성
• 순서대로 저장된 벨류값을 담은 배열을 리턴할 것

2. 시도

• value를 탐색해서 빈 배열에 담아주고 리턴하기로 하고
• 처음 시작하는 루트의 벨류를 빈 배열에 담아주고 시작하자
• 이프문으로 분기를 정하고 재귀를 돌리려고 했음
• 칠드런이 있으면 벨류를 찾아서 담고, 없을 때까지
• 문제는 중복되는 값을 베재할 방법을 못 떠올림
• 그러던중 forEach가 떠오름, 배열에서만 작동 가능, 칠드런은 배열임

3. 수도코드

let dfs = function (node) {
  // 결과를 담을 empty 배열을 하나 선언해서 서치한 값을 담아주자
  // 노드의 벨류 값을 먼저 담아주고 시작하자
  // 칠드런이 있는지 체크하고 칠드런의 벨류값을 푸쉬해주고 
  // 칠드런이 없다면 다음 노드를 탐색해야 하는데
  // forEach를 써서 접근하고, 벨류값만 찾아서 담아주고
  // 다 돌고나서 결과를 리턴하면 될거 같은데...
  // node 자체는 객체이고, node.children은 배열이니
  // forEach는 칠드런에서 돌려야하고
  // 노드의 벨류를 리절트에 푸쉬하는걸 재귀로 돌리면
  // 칠드런을 또 새로운 노드로 인식하고, 노드의 벨류값을 담는 것처럼
  // 칠드런의 벨류값을 뽑아서 담아줄거고
  // 그 값을 리턴하면 [value]의 형태로 리턴하니까
  // 재귀 안에서의 리턴값을 원본의 리절트 값에 푸쉬하면 되나
  // 그냥 푸쉬하지 말고 컨켓하거나 스프레드해서 푸쉬하면 되네
  let result = [];
  result.push(node.value)
  node.children.forEach(el => {
    result.push(...dfs(el))
  })
  return result
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

4. 레퍼런스

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let values = [node.value];

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

  return values;
};