Algorithm 17 : treeDFS

설명

임의의 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]

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

생각

풀이

const result = []
const recursive = function(node) {
  if(node.children) {
    result.push(node.value)
    for(let i=0;i<node.children.length;i++){
      recursive(node.children[i])
    }
    }else{
      result.push(node.value)
    }
  }
  recursive(node)
  return result
};

깨달은 점

DFS를 이해하기 어려웠는데, recursive 함수를 만들었다.
node의 value를 담고 children이 있으면 거기에 재귀함수를 적용하는 과정을 담았다. DFS를 더 공부해야겠다.